【最小树形图|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