LOJ#2052.|LOJ#2052. 「HNOI2016」矿区（平面图转对偶图） LOJ#2052.「HNOI2016」矿区（平面图

题面 【LOJ#2052.|LOJ#2052. 「HNOI2016」矿区（平面图转对偶图）】传送门
题解总算会平面图转对偶图了……
首先我们把无向边拆成两条单向边，这样的话每条边都属于一个面。然后把以每一个点为起点的边按极角排序，那么对于一条边\((u,v)\)，我们在所有以\(v\)为起点的边中找到\((v,u)\)的前缀，这条边就是\((u,v)\)的下一条边了。不断重复这个过程直到找到的区域封闭为止
建好对偶图之后，我们对于每一个点，算出这个点所代表的区域的面积。对于无界域（就是外围无限的那个面），它的面积会是一个负数。那么我们找到这个无界域代表的节点之后，以它为根，求出对偶图的一棵生成树，并记录一下子树里的矿区面积和以及矿区面积平方和
然后考虑询问，对于每一条出现的边，如果是非树边就忽略，否则如果这条边所在的面是它的反边所在的面的儿子，我们就加上这个子树的贡献。否则就减去反边所在的面的子树的贡献。这个画一画图应该就出来了

//minamoto #include #define R register #define ll long long #define pb push_back #define IT vector::iterator #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1; iI; --i) #define go(u) for(int i=head[u],v=e[i].v; i; i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++; } int read(){ R int res,f=1; R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0'; (ch=getc())>='0'&&ch<='9'; res=res*10+ch-'0'); return res*f; } char sr[1<<21],z[20]; int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1; } void print(R ll x){ if(C>1<<20)Ot(); if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z); sr[++C]=' '; } const int N=2e5+5,M=1.2e6+5; const double eps=1e-10; inline int sgn(R double x){return x<-eps?-1:x>eps; } inline double abs(R double x){return x<-eps?-x:x; } struct node{ int x,y; inline node(){} inline node(R int xx,R int yy):x(xx),y(yy){} inline node operator +(const node &b)const{return node(x+b.x,y+b.y); } inline node operator -(const node &b)const{return node(x-b.x,y-b.y); } inline ll operator *(const node &b)const{return 1ll*x*b.y-1ll*y*b.x; } }p[N]; struct Eg{ int id,u,v; double ang; inline Eg(){} inline Eg(R int ii,R int uu,R int vv,R double aa=0){id=ii,u=uu,v=vv,ang=aa; } inline bool operator <(const Eg &b)const{return sgn(ang-b.ang)?angh[N],tr[M]; int tot=1,cnt,rt; IT it; int nxt[M],pos[M],fa[M],vis[M],is[M],st[M]; ll s[M],ss[M],ans1,ans2; int n,q,m,top; void add(R int u,R int v){ ++tot,e[tot]=Eg(tot,u,v,atan2(p[v].y-p[u].y,p[v].x-p[u].x)); h[u].pb(e[tot]); } void build(){ fp(i,1,n)sort(h[i].begin(),h[i].end()); for(R int i=2,v=e[i].v; i<=tot; ++i,v=e[i].v){ it=lower_bound(h[v].begin(),h[v].end(),e[i^1]); if(it==h[v].begin())it=h[v].end(); nxt[i]=(--it)->id; } for(R int i=2; i<=tot; ++i)if(!pos[i]){ pos[i]=pos[nxt[i]]=++cnt; for(R int j=nxt[i],u=e[j].u,v=e[j].v; v!=e[i].u; j=nxt[j],pos[j]=cnt,u=e[j].u,v=e[j].v) s[cnt]+=(p[u]-p[e[i].u])*(p[v]-p[e[i].u]); if(s[cnt]<=0)rt=cnt; } fp(i,2,tot)tr[pos[i]].pb(Eg(i,pos[i],pos[i^1])); } void dfs(int u,int lst){ fa[u]=lst,ss[u]=s[u]*s[u],s[u]<<=1,vis[u]=1; for(int i=0,sz=tr[u].size(),v; iid; if(!is[w])continue; fa[pos[w]]==pos[w^1]?(ans1+=ss[pos[w]],ans2+=s[pos[w]]):(ans1-=ss[pos[w^1]],ans2-=s[pos[w^1]]); } g=__gcd(ans1,ans2),ans1/=g,ans2/=g; print(ans1),print(ans2),sr[C]='\n'; } return Ot(),0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10697368.html