P8529 - The Surveying

内存限制：128 MB 时间限制：5 S

题面：传统评测方式：文本比较上传者：

提交：1 通过：1

As we know, Civil Engineering is the best specialty in the world. To transfer from Computer Science to Civil Engineering, Kuki needs to preview Surveying, the compulsory course.

There are $m$ buildings in this city. Each building can be regarded as a rectangle. The four vertices of the retangle are the Detail Points.

Before starting measurement, Kuki found $n$ positions and would set some of these positions as Control Points. At a Control Point, Kuki can measure all positions within the field of vision. A position can be measured if there is nothing (building or Detail Point) on the segment between this position and a Control Point. In addition, every Control Point should be measured by at least one other Control Points.

Kuki wants to set the mininum number of Control Points to survey all Detail Points. Please help her solve this problem.

Each test contains multiple test cases. The first line contains the number of test cases $T (1 \leq T \leq 10)$ . Description of the test cases follows.

The first line of the input contains two integers nand $(1 \leq n \leq 20, 1 \leq m \leq 100)$ indicating the number of stations and the number of buildings.

For the following lines, the -th line contains two integers $x_{i}$ and $y_{i}$ $(- 2 \times 1 0^{6} \leq x_{i}, y_{i} \leq 2 \times 1 0^{6})$ indicating that the coordinate of the -th station.

For the following $m$ lines, the -th line contains eight integers $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}, x_{i 3}, y_{i 3}, x_{i 4}, y_{i 4}$ $(- 2 \times 1 0^{6} \leq x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}, x_{i 3}, y_{i 3}, x_{i 4}, y_{i 4} \leq 2 \times 1 0^{6})$ indicating that the four vertices of the -th building. The coordinates are given in counter-clockwise order starting from the top-right corner. It's guaranteed that the boundaries of buildings are parrallel to the coordinate axes. Any two buildings will not intersect or contain. Building boundaries will not overlap.

It's guaranteed that the stations will not be inside or on the boundary of buildings.

For each test case:

If it's impossible to measure all Detail Points, print "No Solution!" in a single line (without quotes).

Otherwise, print one interger in one line indicating the mininum number of Control Points

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

8529: The Surveying

题目描述

输入格式

输出格式

输入样例复制

输出样例复制