首页 > ACM题库 > HDU-杭电 > hdu 3370 Guard待解决[解题报告]C++
2014
03-16

hdu 3370 Guard待解决[解题报告]C++

Guard

问题描述 :

You got a new guard offer yesterday. Now you are at the company, and your boss asks you to stand at somewhere to do your job — guard.
You can treat the building as a simple polygon, and your job is finding a position to make sure that you can see the largest area. Please notice that, you have a range of vision, that you cannot see what is out of that range. The wall of building can also block your sight.
Robot
Look at that image; if you stand at the middle then you can see the gray area.

输入:

The input consists of multiple test cases. The first line of each case contains two integers n (0 <= n <= 10) and r(0 <= r <= 100). The next n lines contain a simple polygon that consists of n points, indicating the building. The absolute value of each coordinate won’t be more than 100.
The last case is followed by a line containing two zeros which should not be processed.

输出:

The input consists of multiple test cases. The first line of each case contains two integers n (0 <= n <= 10) and r(0 <= r <= 100). The next n lines contain a simple polygon that consists of n points, indicating the building. The absolute value of each coordinate won’t be more than 100.
The last case is followed by a line containing two zeros which should not be processed.

样例输入:

3 1
0 0
2 0
0 2

3 1
0 0
1 0
0 1
0 0

样例输出:

1.81
0.50


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.