gougou1002
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
1002 Farmland
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1030
35 2006-07-07 10:10:40 00:00.02 888K C++ glimpse
枚举所有的回路，这些回路自然构成了一个多边形，然后判是否有回路以外的点落在这个多边形内。
然而这样做是会得到wa的。看一下下面的情况：
~~该文件已在地震中消失了~~
再把这种情况也判掉，这道题基本上就差不多了。
枚举回路传说有比较好的方法，但我比较土，用的就是普通的dfs。因为回路自然构成了凸包，所以用判点在在凸多边内的方法就可以了。不过我用的是点在任意多边形内的判别方法，两个算法的时间复杂度都是O(n)。后一种方法的具体步骤可以在算法导论计算几何部分找到。
集训期间yext同学发了一道这道题的解题报告，介绍了这道题的标准做法。YM一下。见附录1。
附一下sghao对我做法的评价：farmland这题数据弱，所以枚举所有多边形也可以通过。 但是去年台北赛区也有差不多的题目，枚举所有多边形是根本不可能通过的。 我们以前做farmland都是放水做的，所以台北那题就不会做了。 后来问上交1队用的什么方法，他们告诉我的就是yext说的方法。
最后，我觉得，对本身不会枚举回路和判点在多边内的同学，用我的方法也未尝不可。
[附录1]
~~该文件已在地震中消失了~~
----
类似的值得参考的题目有ZOJ2361 Areas ( http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2361 )，我的解体报告在 http://watashi.ws/blog/970/andrew-stankevich-3-solution/1002 Farmland
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1030
35 2006-07-07 10:10:40 00:00.02 888K C++ glimpse
枚举所有的回路，这些回路自然构成了一个多边形，然后判是否有回路以外的点落在这个多边形内。
然而这样做是会得到wa的。看一下下面的情况：
该文件已在地震中消失了
再把这种情况也判掉，这道题基本上就差不多了。
枚举回路传说有比较好的方法，但我比较土，用的就是普通的dfs。因为回路自然构成了凸包，所以用判点在在凸多边内的方法就可以了。不过我用的是点在任意多边形内的判别方法，两个算法的时间复杂度都是O(n)。后一种方法的具体步骤可以在算法导论计算几何部分找到。
集训期间yext同学发了一道这道题的解题报告，介绍了这道题的标准做法。YM一下。见附录1。
附一下sghao对我做法的评价：farmland这题数据弱，所以枚举所有多边形也可以通过。 但是去年台北赛区也有差不多的题目，枚举所有多边形是根本不可能通过的。 我们以前做farmland都是放水做的，所以台北那题就不会做了。 后来问上交1队用的什么方法，他们告诉我的就是yext说的方法。
最后，我觉得，对本身不会枚举回路和判点在多边内的同学，用我的方法也未尝不可。
[附录1]
该文件已在地震中消失了
类似的值得参考的题目有ZOJ2361 Areas ( http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2361 )，我的解体报告在 http://watashi.ws/blog/970/andrew-stankevich-3-solution/