#P9175. The Surveying

    ID: 5257 传统题 7000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2100提高区间求交有理数精确运算全子集枚举子集 DP位集求并2022杭电多校

The Surveying

The Surveying

题目描述

众所周知,土木工程是世界上最好的专业。为了从计算机科学转到土木工程,Kuki 需要预习必修课《测量学》。

这座城市中有 mm 栋建筑,每栋建筑都可以看作一个矩形。矩形的四个顶点称为碎部点(Detail Points)。

开始测量前,Kuki 找到了 nn 个位置,并准备选择其中一些作为控制点(Control Points)。在一个控制点处,Kuki 可以测量视野范围内的所有位置。如果某个位置与控制点之间的开线段没有碰到任何建筑或其他碎部点,那么这个位置就可以被测量。此外,每个控制点都必须能被至少一个其他控制点测量。

Kuki 希望设置最少的控制点,以测量所有碎部点。请帮助她解决这个问题。

输入格式

每个测试包含多组测试用例。第一行包含测试用例数 TT(1≤T≤101 \le T \le 10),接下来是各组测试用例的描述。

每组测试用例的第一行包含两个整数 nn 和 mm(1≤n≤201 \le n \le 20,1≤m≤1001 \le m \le 100),分别表示候选测站的数量和建筑的数量。

接下来 nn 行,第 ii 行包含两个整数 xix_i 和 yiy_i(−2×106≤xi,yi≤2×106-2 \times 10^6 \le x_i,y_i \le 2 \times 10^6),表示第 ii 个测站的坐标。

接下来 mm 行,第 ii 行包含八个整数 $x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},x_{i4},y_{i4}$($-2 \times 10^6 \le x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},x_{i4},y_{i4} \le 2 \times 10^6$),表示第 ii 栋建筑的四个顶点。坐标从右上角开始按逆时针顺序给出。

保证建筑的边界平行于坐标轴。任意两栋建筑不会相交,也不会相互包含。建筑的边界不会重叠。

保证测站不在建筑内部或边界上。

输出格式

对于每组测试用例:

如果无法测量所有碎部点,在一行中输出 No Solution!(不含引号)。

否则,在一行中输出一个整数,表示所需控制点的最少数量。

样例

1
3 3
2 1
2 14
8 14
7 6 3 6 3 3 7 3
7 12 3 12 3 8 7 8
13 9 9 9 9 4 13 4
3

提示

原文附有样例示意图:在平面直角坐标系中,用黑色矩形表示三栋建筑,用红色空心圆标出三个测站,用红色线段连接可互相测量的控制点,用蓝色线段展示控制点对建筑顶点的测量。

来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。

原 PDF 题面