最小树形图|bzoj 2960 跨平面 平面图转对偶图 最小树形图

【最小树形图|bzoj 2960 跨平面 平面图转对偶图 最小树形图】平面图转对偶图就是枚举每一条没选过的边,每次找反边顺时针方向最近的一条边,这样就可以找到每一个简单多边形(包括最大的多边形)
这个可以用set维护。
注意找完后一条边后不要删!!!!!!!!!!! 然后跑最小树形图就行了。

#include using namespace std; #define N 10005 #define M 10005 int n,m,cnt,top,tot,num; int X[N],Y[N],v[M],bel[M],st[M]; int in[N],pre[N],id[N],vis[N]; struct line { int x,y,id; double alp; line(){} line(int x,int y,int id):x(x),y(y),id(id) {alp=-atan2(Y[y]-Y[x],X[y]-X[x]); } friend bool operator < (const line &l1,const line &l2) {return l1.alpse[N]; set::iterator it; struct edge { int x,y,v; edge(){} edge(int x,int y,int v):x(x),y(y),v(v){} }e[M]; int zhuliu(int root,int n,int m) { int tn,tm,ret=0; while(1) { for(int i=1; i<=n; i++)in[i]=2e9,pre[i]=0; for(int i=1; i<=m; i++) if(e[i].v

    推荐阅读