求大牛讲解平面图
noip吧
全部回复
仅看楼主
level 8
Bull_林 楼主
平面图中如何记录任意一个域其周围的点和边？
2013年05月15日 07点05分 1
level 10
Delostik
一般不都是有规律的么[我错了]
2013年05月15日 07点05分 2
wwwaaannngggrs
要是有规律的话我THUSC就不会那样了。。
2013年05月15日 09点05分
Delostik
回复 wwwaaannngggrs :[我错了]
2013年05月15日 09点05分
level 8
Bull_林 楼主
？我的意思是给出一个用邻接表存储的一个平面图
算出任意一个域其周围的点和边（用dfs?）
还有， 这是为了建对偶图做准备
2013年05月15日 07点05分 3
level 12
wyl8899
wenku.baidu.com/view/9daf5a1e55270722192ef7b1.html
2013年05月15日 08点05分 4
level 10
成成8924
把每条边拆成两条边
每个点出发的边按斜率排序（即顺时针/逆时针）
像种子染色一样的做，从某个没有走过的边出发，走到他的反边的顺时针/逆时针方向的下一条边。一直到回到这条边打止
最后会有无穷大的域。注意到他的正负号跟其他的有向面积的符号不同（有向面积是用叉积计算的，叉积取决于正负号）
例题：
Bzoj 1036
Bzoj 3051
前者容易一些
2013年05月19日 02点05分 5
Bull_林
果然牛人， 差不多懂了 看来我还是先做做有规律的题吧[88]
2013年05月19日 07点05分
1