首页 > ACM题库 > HDU-杭电 > hdu 3702 The Covering Polygon待解决[解题报告]C++
2015
02-21

hdu 3702 The Covering Polygon待解决[解题报告]C++

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.

输出:

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.

样例输入:

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


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。