bzoj3051[WC2013]平面图（树上倍增+平面图转对偶图+扫描线） bzoj3051[WC2013]平面图（树上倍增

简要题意：二维平面上n个点，点之间有一些连线，连线不在点之外的地方相交，将平面分为若干个区域。给出一些询问点对，问从这个点所在的区域走到另一个点所在的区域的最小代价。
题解：这道题首先可以把平面图转对偶图，这一点比较容易发现。然后对于从左指向右的线段，运用扫描线的思想，扫到左端点加入平衡树，扫到右端点从平衡树中删除。因为两线互不相交，所以相对位置不变。然后建立平面直角坐标系，y轴可以随意左右平移。对于每一条线段，我们使右端点正好在y轴上，然后选择两线段左端点x坐标比较大的作为比较直线，计算这条直线与两线段的交点的高低。然后就是一堆细节。真实的码农题。我写了3个namespace不然受不了

#include using namespace std; const int N=1e5+7,inf=1e9; const double eps=1e-8; int n,m,q,num,bel[N<<1]; struct edge{int v,nxt,w,id; }e[N<<1]; struct Edge{int u,v,w; double o; }d[N<<1]; struct point{ int x,y,id; void init(int i) { double xx,yy; scanf("%lf%lf",&xx,&yy); x=(int)(xx*2+eps),y=(int)(yy*2+eps),id=i; } }p[N],Q[N<<1]; struct node{int x,y,t; }; bool operator<(node a,node b){return a.x!=b.x?a.xd[j].o; int x=max(p[d[i].u].x,p[d[j].u].x); double x1=1.0*(p[d[i].v].y-p[d[i].u].y)*(x-p[d[i].v].x)/(p[d[i].v].x-p[d[i].u].x)+p[d[i].v].y; double x2=1.0*(p[d[j].v].y-p[d[j].u].y)*(x-p[d[j].v].x)/(p[d[j].v].x-p[d[j].u].x)+p[d[j].v].y; return x1>x2; } }; setS; node a[N<<3]; int cnt=0; void work() { for(int i=2; i<=(m<<1)+1; i++) if(p[d[i].u].x1},a[++cnt]=(node){p[d[i].v].x,i,0}; for(int i=1; i<=q; i++)a[++cnt]=(node){Q[i].x,i,2},a[++cnt]=(node){Q[i+q].x,i+q,2}; sort(a+1,a+cnt+1); for(int i=1; i<=cnt; i++) if(!a[i].t)S.erase(a[i].y); else if(a[i].t==1)S.insert(a[i].y); else{ p[n+1]=(point){a[i].x,Q[a[i].y].y,0}; p[n+2]=(point){a[i].x-1,Q[a[i].y].y,0}; d[(m<<1)+2]=(Edge){n+1,n+2,0,atan2(p[n+2].y-p[n+1].y,p[n+2].x-p[n+1].x)}; S.insert((m<<1)+2); set::iterator it=S.find((m<<1)+2); if(it!=S.begin())bel[a[i].y]=e[*--it].id; else bel[a[i].y]=1; S.erase((m<<1)+2); } } } namespace Graph{ int cnt=1,hd[N],nxt[N<<1]; vectordouble,int> >G[N]; point s=(point){inf,inf,0}; void adde(int x,int y,int z) { e[++cnt]=(edge){y,hd[x],z,-1},hd[x]=cnt; e[++cnt]=(edge){x,hd[y],z,-1},hd[y]=cnt; } void dosort(int x) { for(int i=hd[x]; i; i=e[i].nxt) G[x].push_back(make_pair(atan2(p[e[i].v].y-p[x].y,p[e[i].v].x-p[x].x),i)); sort(G[x].begin(),G[x].end()); int sz=G[x].size(); for(int i=0; i1]=G[x][(i+1)%sz].second; } void find(int x){for(int i=x; e[i].id<0; i=nxt[i])e[i].id=num; } void work() { cnt=1; for(int i=1; i<=n; i++) { p[i].init(i); if(s.x>p[i].x||s.x==p[i].x&&s.y>p[i].y)s=p[i]; } for(int i=1,x,y,z; i<=m; i++) { scanf("%d%d%d",&x,&y,&z); d[i<<1]=(Edge){x,y,z,atan2(p[y].y-p[x].y,p[y].x-p[x].x)}; d[(i<<1)+1]=(Edge){y,x,z,atan2(p[x].y-p[y].y,p[x].x-p[y].x)}; adde(x,y,z); } scanf("%d",&q); for(int i=1; i<=q; i++)Q[i].init(i),Q[i+q].init(i+q); for(int i=1; i<=n; i++)dosort(i); num=1; find(G[s.id][0].second); for(int i=1; i<=cnt; i++)if(e[i].id<0)++num,find(i); for (int i=2; i<=cnt; i+=2) if(e[i].id!=1&&e[i^1].id!=1)MST::add(e[i].id,e[i^1].id,e[i].w); else MST::add(e[i].id,e[i^1].id,inf); } } int main() { scanf("%d%d",&n,&m); Graph::work(); ScanLine::work(); MST::work(); }

【bzoj3051[WC2013]平面图（树上倍增+平面图转对偶图+扫描线）】转载于:https://www.cnblogs.com/hfctf0210/p/10706391.html