最小左转法|UOJ#57:[WC2013]平面图（最小左转法+点定位）平衡树|点定位|扫描线

传送门

在一个平面图中有n个顶点和m条直线段，第i个顶点的坐标为(xi,yi) ，第j条直线段连接顶点uj和顶点vj 。权值为hj ，除顶点uj和vj外直线段j不经过其他的顶点。任意两条直线段如果存在公共点，则该公共点一定是一个顶点，此时这两条直线段都会连接这个顶点。对于任意的两个顶点x和y ，总是可以找到一顶点序列a1,a2,…,ak使得a1=x,ak=y且对于任意1≤i 这m条直线段将整个平面分成了若干个区域，其中只有一个区域是无穷大的，其余均是有界的，我们称无穷大的区域为禁区。
现在给出q次询问，每次给定平面中的任意两个不是顶点且分别不在任意一条直线段上的点A和B ，请画一条曲线连接A和B ，要求曲线不能经过禁区以及任何顶点，并使得穿过的直线段中权值最大的尽可能小。你需要对每次询问回答这个值最小为多少。

题解：
如果你写过BZOJ1035的 mlogm 写法的话这道题就很简单了。
首先最小左转法找出平面，每条边看做平面间的连边，建出 MST 。
把每个点离线下来做点定位，用扫描线+平衡树。
【最小左转法|UOJ#57:[WC2013]平面图（最小左转法+点定位）】最后倍增求树上最小值就好了（当然你也可以 LCT 或者树链剖分）。

#include using namespace std; typedef long long ll; inline int read(){ char ch=getchar(); int i=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0'; ch=getchar(); } return i*f; } inline void W(int x){ static int buf[50]; if(!x){putchar('0'); return; } if(x<0){putchar('-'); x=-x; } while(x)buf[++buf[0]]=x%10,x/=10; while(buf[0])putchar(buf[buf[0]--]+'0'); } const int Maxn=2e5+50; const double eps=1e-12; inline int sgn(double x){return (x>eps)-(x<-eps); } int n,m,vis[Maxn],tot=1,A[Maxn],B[Maxn],bl[Maxn],Pcnt,ec,anc[Maxn],q,cnt; inline int getanc(int x){return (x==anc[x])?x:(anc[x]=getanc(anc[x])); } struct L{ int a,b,id,val; L(){} L(int a,int b,int id,int val):a(a),b(b),id(id),val(val){} }l[Maxn]; struct P{ double x,y; P(double x=0,double y=0):x(x),y(y){} friend inline P operator -(const P &a,const P &b){return P(a.x-b.x,a.y-b.y); } friend inline double operator *(const P &a,const P &b){return a.x*b.y-a.y*b.x; } inline double slope(){return atan2(y,x); } }p[Maxn<<1]; struct E{ int a,b,val; E(int a=0,int b=0,int val=0):a(a),b(b),val(val){} friend inline bool operator <(const E &a,const E &b){return a.val=0; i--) if(d&(1<=0; i--){ if(fa[x][i]!=fa[y][i]){ mn=max(mn,max(mx[x][i],mx[y][i])); x=fa[x][i],y=fa[y][i]; } } return max(mn,max(mx[x][0],mx[y][0])); } }gr; struct cp{ inline bool operator ()(const pair &a,const pair &b){ int t=sgn(a.first-b.first); if(t)return t<0; else return a.second,cp >g[Maxn]; namespace Scanline{int tc,vis[Maxn]; struct T{ int a,b,u,id; T(int a=0,int b=0,int u=0,int id=0):a(a),b(b),u(u),id(id){} friend inline bool operator <(const T &a,const T &b){ if(a.a==b.a)return a.u>b.u; if(p[a.a].x!=p[b.a].x)return p[a.a].xreturn p[a.a].y>p[b.a].y; } }t[Maxn<<1]; struct cmp{ inline bool operator ()(const T &a,const T &b){ if(a.a==a.b)return (p[b.b]-p[a.a])*(p[b.a]-p[a.a])<0; if(b.a==b.b)return (p[a.a]-p[b.a])*(p[a.b]-p[b.a])<0; double t1=(p[a.a]-p[b.b])*(p[a.b]-p[b.b]),t2=(p[a.a]-p[b.a])*(p[a.b]-p[b.a]); double t3=(p[b.a]-p[a.a])*(p[b.b]-p[a.a]),t4=(p[b.a]-p[a.b])*(p[b.b]-p[a.b]); return (t1<-eps&&t2eps&&t4>-eps)||(t4>eps&&t3>-eps); } }; setS_l; int st[Maxn<<1],tp; inline double area(){ double res=0; for(int i=1; i<=tp; i++)res+=p[l[st[i]].a]*p[l[st[i]].b]; return res; } inline int getsuf(int now){ int b=l[now].b,a=l[now].a; double ang=(p[a]-p[b]).slope(); set< pair >::iterator it=g[b].lower_bound(make_pair(ang,0)); if(it==g[b].begin())return (--g[b].end())->second; else return (--it)->second; } inline void dfs(int x){ vis[x]=1; int t=l[x].b; st[++tp]=x; int suf=getsuf(x); if(vis[suf]){ t=(area()>0)?(++Pcnt):0; for(; tp>=1; --tp){ bl[st[tp]]=t; x=st[tp]; int a=l[x].a,b=l[x].b; g[a].erase(make_pair((p[b]-p[a]).slope(),st[tp])); } }else dfs(suf); } inline void getarea(){ for(int i=2; i<=tot; i++)if(!vis[i])dfs((tp=0,i)); for(int i=2; i<=tot; i++) if(p[l[i].a].x0,i); t[++tc]=T(l[i].b,l[i].a,2,i); } for(int i=1; i<=q; i++)t[++tc]=T(i*2+n-1,i*2+n-1,1,i),t[++tc]=T(i*2+n,i*2+n,1,i); sort(t+1,t+tc+1); for(int i=1; i<=tc; i++){ if(t[i].u==2)S_l.erase(T(t[i].b,t[i].a,0,0)); //,print(); else if(t[i].u==0)S_l.insert(t[i]); //,print(); else{ set::iterator it=S_l.lower_bound(t[i]); if(it==S_l.begin())continue; --it; int s=(t[i].a-n); (s&1?A[(s+1)/2]:B[(s+1)/2])=bl[(it)->id^1]; } } }}int main(){ n=read(),m=read(); for(int i=1; i<=n; i++)p[i].x=read(),p[i].y=read(),++cnt; for(int i=1; i<=m; i++){ int x=read(),y=read(),w=read(); ++tot; l[tot]=L(y,x,tot,w); g[y].insert(make_pair((p[x]-p[y]).slope(),tot)); ++tot; l[tot]=L(x,y,tot,w); g[x].insert(make_pair((p[y]-p[x]).slope(),tot)); } q=read(); for(int i=1; i<=q; i++){ ++cnt; scanf("%lf%lf",&p[cnt].x,&p[cnt].y); ++cnt; scanf("%lf%lf",&p[cnt].x,&p[cnt].y); } Scanline::getarea(); for(int i=2; i<=tot; i+=2) if(bl[i]&&bl[i^1])e[++ec]=E(bl[i],bl[i^1],l[i].val); sort(e+1,e+ec+1); for(int i=1; i<=Pcnt; i++)anc[i]=i; for(int i=1; i<=ec; i++){ if(getanc(e[i].a)==getanc(e[i].b))continue; gr.add(e[i].a,e[i].b,e[i].val); gr.add(e[i].b,e[i].a,e[i].val); anc[getanc(e[i].a)]=getanc(e[i].b); } for(int i=1; i<=Pcnt; i++)if(!gr.id[i])++gr.ind,gr.dfs(i); for(int i=1; i<=q; i++)W(gr.query(A[i],B[i])),putchar('\n'); }