The Covering Polygon

Martians are invading the earth! Yes, it's not an illusion, it's the truth. Their attack are so quickly and unpredictable that few people realize it until many most buildings are destroyed. As a human being on the earth, you feel it's your duty to protect your homeland.

After scouting, you find there are some powerful weapons which are still working well on the land. They are the last hope to defeat the Martains, so all of them should be protected. And there are a few of defensive devices can be used. If you activate these devices in the order D1, D2, .., Dn, then there will be a laser line between D1 and D2, D2 and D3, ..., Dn and D1, which forms a polygon. Everything enclosed by the polygon or laid on the boundary can be protected well. Due to some physical reasons, nonadjacent laser lines can not intersect (even intersect at end points), or they will disappear and leave a hole in the polygon, which Martains can go through to destroy everything. Of course, no devices can be activated two or more times.

The final wave of Martains is near, so you need design a plan to construct our defence quickly. Activating a defensive device is very hard and time-consuming, so you should active as few as possible to protect all the weapons. You have the ability, and you have the duty, too.

The beginning of the input is an integer T (T <= 30), which is the number of test cases. T cases are followed. The first line of each test case is two integers sizeA (3 <= sizeA <= 500) and sizeB (3 <= sizeB <= 200000), which denote the number of defensive devices and the number of weapons respectively. Each of them can be considered as a point in 2D euclid plane. The next sizeA+sizeB lines are positions of devices and weapons, each of which contains two integers describing its x and y coordinates. The first sizeA lines are points of defensive devices, and the last sizeB lines are points of weapons.

The absolute value of all coordinates are not greater than 10^8. Positions of any two objects in the same test case are distinct. Because of some strange reasons, not all of the weapons are on the same line.

For each test case, print a line contains a single integer which is the least devices to be actived to protect all weapons. If all weapons can not be protected, output -1 instead.

2

4 3
1 1
2 2
3 3
4 4
5 5
6 6
7 9

7 3
0 5
5 0
-5 0
100 100
-100 -100
100 -100
-100 100
0 0
0 1
1 1

-1
3

wywcgs @ HIT & XMU

HDOJ 5th Anniversary Contest