首页 > ACM题库 > HDU-杭电 > hdu 3099 Defense of the Ancients待解决[解题报告]C++
2014
03-02

hdu 3099 Defense of the Ancients待解决[解题报告]C++

Defense of the Ancients

问题描述 :

DotA? I’m afraid you’ve got a wrong impression, because we are talking about some real Ancients.
A lot of towers are in the first quadrant of rectangular coordinates. And between every two towers there is a wall. All of them are Ancients. Somehow, some skytroopers are trying to attack our Ancients and all we know is that they’ll land at the second, third and fourth quadrant of rectangular coordinates. Because those areas are desolation, the troops decided to follow a fixed straight line. Now we’ve got all the landing coordinates of the troops and the polar angle of their walking lines. To protect our Ancients, we need to know where the troops will first arrive at the Ancients.
Life Game

输入:

There are multiple test cases.
First line contains a single integer T (T<=10), indicates the number of test cases.
For each test case:
The first line has two positive integers N and M (1<N<=100000, M<=100000), represent the number of towers and skytroopers.
Following N lines, each line contains two integers X and Y, represents the coordinate of the tower.
Following M lines, each line has three integers SX, SY and XITA, indicates the coordinates of a skytrooper and the polar angle of their attacking line (in degrees). SX and SY will not bigger than 0 at the same time.
All the coordinates values lies in [-20000, 20000]. No two towers will be in same place.

输出:

There are multiple test cases.
First line contains a single integer T (T<=10), indicates the number of test cases.
For each test case:
The first line has two positive integers N and M (1<N<=100000, M<=100000), represent the number of towers and skytroopers.
Following N lines, each line contains two integers X and Y, represents the coordinate of the tower.
Following M lines, each line has three integers SX, SY and XITA, indicates the coordinates of a skytrooper and the polar angle of their attacking line (in degrees). SX and SY will not bigger than 0 at the same time.
All the coordinates values lies in [-20000, 20000]. No two towers will be in same place.

样例输入:

1
6 3
5 1
8 5
13 2
14 7
7 9
1 7
-2 -2 45
8 -2 90
-3 7 120

样例输出:

3.400000 3.400000
8.000000 1.375000
safe


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢