uoj#57. 【WC2013】平面图

题意
【线段树|uoj#57./bzoj3051 【WC2013】平面图 //平面图转对偶图】给出由M(<=1e5)条带权线段连接的N(<=1e5)个点，点横纵坐标为整数且在[0,1e7]间。线段只在顶点处相交。
Q(<=1e5)组询问，每组询问给定两个不在前述任意线段上的点A,B，满足其横纵坐标为0.5的奇数倍。
要求画一条不经过无界区域或顶点的曲线连接A,B，并使得其横穿的线段权值最大的最小。
判断是否有解，输出最优解下经过线段的最大权值。

题解
这道题的题解还是暑假学网络流的时候看到的…。
是一个听起来很高端实际上很暴力的东西。
几周前的模拟考了类似的东西，是平面图转对偶图套个动态点分治我当场竟然写出来了 结果又T又RE又MLE
扯远了…。进入正题。
一个显然的思路：
在每条线段两侧的有界区域间连边，值为线段的权值。
于是我们只需要对这堆区域建一个最小生成树，每次询问时树上倍增跳一跳就好了。
不过有一些令人恼火的实现问题，比如线段两侧分别对应哪个区域，或怎么确定A,B在哪个区域里。
第一个问题可以计算几何常识解决。
从一条边开始，每次走它终点的出边里与它顺（逆）时针夹角最小的，这么走一圈就是一个区域。
所以我们对每个点的出边极角排序，就可以处理出每条边应走的下一条边。
鉴于每条线段只会被正着走一次反着走一次，所以直接搜一下，能够知道每条边左（右）对应的区域。
因为带个排序，所以这一步是O(nlogn)的。
考虑第二个问题。
设当前询问点坐标为(Ax,Ay)，画一条x=Ax的直线穿过一些线段，找到其中交点纵坐标第一个大于Ay的。这条线段下侧的区域即为所求。
这个事情可以拿个数据结构来维护。我们把每一条线段挂在 它在x方向上覆盖的区间 在线段树中所对应的log个节点上。
因为线段除顶点不交，它们在y方向上的相对位置必然不变。我们把每个节点挂着的线段排个序，查询就是按照Ax在线段树上单点查询，然后在log个节点包含的线段里二分出与x=Ax交点纵坐标大于Ay且最小的。
顺便，可以通过查一个横坐标在中间纵坐标为-1的点确定无界区域。
这里是O(nlog^2n)的。
最后是O(nlogn)的最小生成树，本题宣告结束。

注意事项
好想但是不大好写。
如果你对自己的码力没有绝对的信心，请在做这道题时确保自己拥有充足的时间和耐心。
可以写一段调一段，以确保不会最后一堆代码放到一起调不出来。
（本来还想写写过程中犯的错误，发现都是一些弱智错误 所以还是算了）

代码
在没删调试数据之前，这份代码长7k…。

#include #define N 100005 #define L 18 using namespace std; typedef long long LL; int n,m,q,to[N<<1],hd[N<<1],len[N<<1],lk[N],cnt=1,ln[N][L], st0[N],st1[N],pre[N<<1],ref[N<<1],ff[N],f[N][L],dep[N], non,t0,t1,tot,cct; //ref是记有向边左侧区域编号的 vectorvec[N<<2]; //我因为这个开小了多调了1h QAQ struct node {int x,y; }a[N]; struct seg {int u,v,w; }b[N]; int getr(int x) {return ff[x]==x?x:ff[x]=getr(ff[x]); } inline void add(int u,int v,int w) {to[++cnt]=v,hd[cnt]=lk[u],len[cnt]=w,lk[u]=cnt; } int i,tp0,tp1,ans; void ins(int k,int l,int r,int ll,int rr) { if(l==ll&&r==rr) {vec[k].push_back(i); return; } int mid=l+r>>1; if(rr<=mid)ins(k<<1,l,mid,ll,rr); else if(ll>mid)ins(k<<1|1,mid+1,r,ll,rr); else ins(k<<1,l,mid,ll,mid),ins(k<<1|1,mid+1,r,mid+1,rr); } double tmp; inline double loc(int x,double xx) { return a[b[x].u].y+(a[b[x].v].y-a[b[x].u].y)/ (double)(a[b[x].v].x-a[b[x].u].x)*(xx-a[b[x].u].x); }//线段x与x=xx的交点 void qry(int k,int l,int r,double x,double y) { int mid=l+r>>1; if(l>1,tp=loc(vec[k][mid],x); if(y>1; cal(k<<1,l,mid),cal(k<<1|1,mid+1,r); } } bool cmp(int x,int y) {return (a[to[x]].x-a[i].x)*(LL)(a[to[y]].y-a[i].y) -(a[to[y]].x-a[i].x)*(LL)(a[to[x]].y-a[i].y)<0; } inline int Q(double x,double y) { tmp=1e8,ans=-1; qry(1,1,t1-1,x,y); return ans<0?non:ref[ans<<1|1]; } bool Cmp(seg x,seg y) {return x.wln[x][j-1]? ln[f[x][j-1]][j-1]:ln[x][j-1]; f[x][j]=f[f[x][j-1]][j-1]; if(!f[x][j])break; } for(int k,j=lk[x]; j; j=hd[j]) if(!dep[k=to[j]]) f[k][0]=x,ln[k][0]=len[j],dfss(k); } double ax,ay; int main() { scanf("%d%d",&n,&m); for(i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y); for(i=1; i<=m; i++) { scanf("%d%d%d",&b[i].u,&b[i].v,&b[i].w); if(a[b[i].u].x>a[b[i].v].x)swap(b[i].u,b[i].v); } sort(b+1,b+m+1,Cmp); for(i=1; i<=m; i++) add(b[i].u,b[i].v,0),add(b[i].v,b[i].u,0); for(i=1; i<=n; i++) { t0=t1=0; for(int j=lk[i]; j; j=hd[j]) if(a[to[j]].yelse st1[t1++]=j; sort(st0,st0+t0,cmp); sort(st1,st1+t1,cmp); for(int j=0; jst1[t1-1])?non:Q(ax,ay); scanf("%lf%lf",&ax,&ay); tp1=(ax<=st1[0]+1e-9||ax+1e-9>st1[t1-1])?non:Q(ax,ay); if(tp0==non||tp1==non||(getr(tp0)^getr(tp1))) {puts("-1"); continue; } if(dep[tp0]=0&&dep[tp0]>dep[tp1]; i--) if(dep[f[tp0][i]]>=dep[tp1]) ans=ans=0; i--) if(f[tp0][i]^f[tp1][i]) ans=ans