over 3 years ago

题目内容请走(中文题你还想不看题。。。)

分析:

做过再做这道题还算有点底了。
我们将每条线段拆成一正一反,然后从任意点出发,走出的每一个环都是一个封闭图形。
具体怎么走,就是对于走到的当前边,找出与其反边顺时针夹角最大的那一个就是我们要走的下一条边。
QQ截图20150817162636.png
另外为了保证我们都是按照逆时针走出的图形,我们需要在走出一个图形后判断其面积是否为负,如果为负那么我们不取这个封闭图形。如果不这样的话,有可能走出两个一模一样的封闭图形,也有可能走出更奇怪的图形。。。
还有两个问题就是如何判断一个点在哪一个封闭图形内,和如何判断一个封闭图形的相邻图形。
对于第一个问题,因为一个点有可能被包含在多个封闭图形内,而我们只取那个最里面的,所以将封闭图形按面积从小到大排序,扫到的第一个就是我们所求。(至于怎么判断一个点在多边形内,从这个点引一根射线,判断与封闭图形的边的相交次数,为奇数证明其在内部,否则在外部。。。)
对于第二个问题,我们扫描一个封闭图形的每条边:如果这条边的反边被选过,那么这条边的反边对应的封闭图形就是相邻的图形之一;如果存在边没有被选过,我们求出包含当前封闭图形的最小的封闭图形也是相邻的图形之一。
好像就差不多了,连改加调用了差不多2h吧。。。
bzoj1035.cpp

← 最小树形图——朱刘算法(poj3164) 线性规划+floyd最小环(bzoj1027) →
 
comments powered by Disqus