为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/fence4
目录 |
[编辑] 分析
几何问题
1.判断多边形是否合法
任两条边都不相交即合法，注意这里的相交是严格相交，顶点相交不算相交。
2.能看到哪些边
设人所在点为o，从o分别到任意边的顶点和中点做射线，设为op，然后求出与op相交的最近一条边，则这条边一定可以被看见。 而对于每条边，它要么被过它中点的射线“看见”，要么被某条边遮住一部分，那么肯定会被过这条边的某个顶点“看见”。 以上是不考虑特殊情况的粗略算法。
需要考虑的特殊情况：
1. o到ab仅有一条边，此时o看不到ab
2. o经过一条平行线到ab，此时o看不到ab
3. o经过一点到ab，此时o看不到ab
针对以上情况，我们设3个变量ml,mr,mm，ml记录交点s到o的最近距离，且s的两条边在op的左侧，mr与ml类似，s的两条边在op的右侧，mm记录横穿op的交点的最近距离。 枚举每条边时，如果这条边横穿op（严格相交），那么更新mm，记录当前的边如果这条边与op交于一个顶点s，那么： (1)如果s的两个相邻顶点在op的两侧（考虑情况1），更新mm，记录边 (2)如果s的两个相邻顶点在op的左侧（或一个在左侧，一个在op上，考虑情况2），那么更新mr (3)类似地更新ml。
最后如果ml和mr都比mm近，那么属于情况1，ab看不见。 这样就ok了。 转自SevenLunar
[编辑] 本题数据较奇怪~
反对上面说可以用二分法，尽管二分法可以ac。为什么不能？因为能看到栅栏不一定能看到栅栏的两个端点之一。 如下面数据： 6 3 0 2 -1 2 1 0 2 6 2 4 1 4 -1 答案应该是4，因为为上面的栅栏可以看见，但是看不到两个端点~
尽管这样的情况没有出现，但数据里出现了只能看见很短的栅栏的数据（Data9）。 （data9，锯齿状）
——phoeagon
二分法并不是直接二分，而是先对射线进行排序后再进行二分，二分之后还要unique一下。这样二分之前，每两条射线中间都没有端点，就不会出现你说的问题了。
二分法其实就是楼下说的扫描法，只是只扫必要的区段。
ps.排序可以直接利用atan2函数
[编辑] 注意
USACO加了第12个点，貌似是对付二分法的
[编辑] 二分法是无辜的。。。
我用的就是二分法 一次就A了 也过了第12个数据 phoeagon兄的数据我输出的也是4个 应该是正确的 详见我的代码 在c++里面 较简短 ---ymfoi Orz Orz
[编辑] 我来说两句
我完全没有接触过计算几何，做这个题，我用的解析几何的方法。直接对过观察点的直线写点斜式方程，枚举倾斜角，对篱笆写两点式方程，求距离最近的交点。 第九个数据有点变态。过不了。经过试验，每隔0.001弧度进行扫描，除第九个由于精度问题无法分辨，其余全过，不超时。每隔0.0001弧度扫描，答案全对但是 第6，7两个点超时。
具体看看我失败的代码。。。。c++ talenth1
一位走过的菜菜。。。我也做出来了，是扫描发，我是对每一条边分成50份扫描，然后对边界扫细致一点就是了，50等分就可以过！偶也！ 每次 for i:=1 to 50 do
t1:=(x2-x1)/100.01*i+x1; t1就是那个我找到的点的横坐标，然后根据k和b生产t2(即y)，然后看和其他线有无严格相交！ 0SAC！
[编辑] 另一种解法——线段覆盖
这道题从读题到写成到AC，我花了将近两天，我并没有使用USACO/NOCOW上的二分法，而是用了线段覆盖的思想（自认为比二分法容易理解）。 详细算法请见USACO 3.4.1 闭合的栅栏 题解
偶细分成了500份，因为处理不好精度问题。还骗了第11个数据。——by 怡红公子
[编辑] 我也说说吧
其实可以从起点过一个顶点做射线,然后略微偏移,如果这两条线都交在后面的一条线上,且中间无其他交点时,后面线段的可以看见.
这种算法没有问题，而且时间/空间/编程复杂度很低。详见【解题报告】USACO Section 3.4 PROB Closed Fences(源代码已发到 参考代码->C++ID:GeorgeG1那个)
--George-Gate
[编辑] 关于计算几何方法
终于ac了这道题，说实话我是看的nocow上的计算几何方法的题解。
计算几何算这道题基本上没有精度问题，而且方法简单。
题解上说的有些复杂了，其实中点是不必要考虑的，因为它着实没有什么特别的地方。 而且题解上在判断特殊情况时用了mm，ml，mr三个变量，其中mm是不必要的，它可以看作两部分，左半部分可以更新ml，右半部分更新mr。
用枚举的话，时间复杂度是O(n^2)，也很快。
[编辑] 二分法的解释
这个二分是对线段的二分，而不是对序列的二分。 假如妨碍到你们看题解了，请把这一段删掉。
[编辑] 极角排序法
可以先以视点为中心对各点极角排序，之后把视点向序列中相邻点的中点连射线，每条射线第一次规范相交的线段可以看到。显然可以包括所有情况。
可以减少边界判断。为了减少一个点挡住视线的可能，可以给射线加微小的偏移量，甚至偏移多次。
见c++ dxmtb代码
加偏移量这一步显然是不必要的：极角排序以后，每个相邻两点与视点的夹角有两种情况, 一种是夹角大于0，这种情况是有意义的。 另外一种是0，视野仅仅是一条线，不需要考察。 所以取夹角大于0的相邻两点的中点，作射线，很显然这样的射线不会经过某个端点。然后只要求第一个相交的线段就是了。
[编辑] 扫描的灵异方法
扫描的时候直接扫描端点，但是让端点在几个方向上随机跳跃很小的距离，在统计人到端点连线上最近的那个栅栏，那个栅栏可以看见
[编辑] 菜鸟废话神牛无视
可不可以用观察点与各边的端点连线段，再排序，然后用与观察点由近到远的线段进行线段覆盖，如果覆盖到了原来没有覆盖到的区域，则是可以看见的。在边界上稍稍注意下就可以了。
如图，线段的顺时针顺序是s1s4,s1s3,s1s2,s1s5(s1是观察点，s2,s3,s4,s5是端点），边由近到远的顺序是s2s3,s3s4,s2s5,s4s5。那么先插入s2s3,再插入s3s4,插入s2s5时发现无覆盖，那么这就是不被看见的边，而s4s5与上同。
两次排序，一次线段覆盖，时间复杂度是（nlogn)
这是一个好的算法。但事实上，其时间复杂度并不能达到 O(n lg n)。 这是因为，把栅栏的边按照由近到远的顺序排列（具体方法参见这里）就需要 Θ(n^2) 时间，并且一开始判断栅栏是否是简单多边形也需要 Θ(n^2) 时间。
p.s. 我不是神牛，因此可以不无视您。。。
---SillyRobot
为什么不从原点开始，360°这么旋转过去啊？可以过的。。 zq
《算法导论》P599 有nlgn的方法解决 “确定任意一对线段是否相交”的问题，所以是可以做到nlgn……
[编辑] 一个没有误差的方法
第一问不解释
第二问枚举每条线段，一开始可见范围为线段的范围，每次用其他线段遮挡这条线段所在直线
注意枚举其他线段时如果按多边形边界顺序枚举，则每一步得到的区间都是连续的，因为边界上两条连续边有一个公共点
遮挡时情况很多，要注意细节
代码很长，见c语言 yyt的代码
代码中区间是用两个端点表示，按坐标排序的，后来才发现可以用两条射线表示，按极角排序
点的坐标用了分数表示，不想用的可以不用
这样代码其实可以写短一点的
再补充一句，我现在觉得代码中那种用三个点表示向量的方法很不好，也许换成两个点表示的可以再短一些
