05 Apr 10 WHU2010校赛预赛J题：Guard

题意：给定一个简单多边形，问内部哪个点可以看到的面积最大。（可视范围是已知的R，也就是说，如果没有遮挡，那个可视面积就是一个半径为R的圆）

这题是我出的另一个复杂几何，说一下做法：经过爬山处理之后，就变成了一个纯粹的几何题，问题：给定一个简单多边形，和一个点，问这个点能看到的面积是多大。

我的做法就是把圆和所有的线段离散化。除了他们交点之外还要用到视线的射线来离散化。

离散化之后就是判断每一个单元小块是不是可见的。。麻烦是麻烦了点，但是思路还是挺清晰的。不知道有没有人有兴趣去做做这个题目。

Filed in Iproblem

Felicia | 06 Apr 2010 10:29 am
摸摸，这不就是USACO上面的题么？高中做USACO的时候遇到的第二个计算几何，被我直接跳过了……

[Reply]
momodi Reply:
April 6th, 2010 at 10:34 am
啊？应该不一样吧。。？你说的那个是可视线段还是什么来着？

[Reply]
Felicia | 06 Apr 2010 10:37 am
那个题说的是有一个多边形栅栏（不一定是凸多边形），有个人站在栅栏外边，问他能看到多少长度的栅栏，所以我说跟你这个挺像的

[Reply]
momodi Reply:
April 6th, 2010 at 10:56 am
嗯。。我知道那个题。。
这个难多了嘛
这个是有可视范围的
就是太远了的看不到

[Reply]