BZOJ3051: [wc2013]平面图 扫描线+可持久化平衡树+Kruskal

题解：

首先处理好区域之间相邻的情况，这构成了一个无向图，我们只要先求一遍最小生成树，然后树上倍增就能得出答案。

那么我们要做的事情就是：

首先搞出所有的区域，并造出无向图；

其次就是询问一个点在哪个区域中。

由于比较弱，现在只会处理所有的点都连通的情况。

首先我们得找出所有的区域，我们将每一条边都拆成两条有向边，然后我们用下面的方式来找出一个区域：

首先找出一条还没有被删除过的有向边，不妨令其起点为$u$，终点为$v$。

如果当前的有向边的终点就是一开始的有向边的起点，则已经找到一个区域，可以直接退出了。

否则考虑所有以$v$为起点的有向边，找出有向边$v->u$逆时针旋转碰到的第一条有向边作为下一条有向边，并删除当前的有向边。

如果找到的下一条有向边已经被删除了，则退出。

在这个过程中，我们顺带记录下每一条有向边右侧区域的编号，并利用叉积算出这个区域的有向面积。

那么能够发现一个有限区域的有向边是顺时针的，有向面积$<0$。

无限区域的有向边是逆时针的，有向面积$>0$。

这样我们就区分出了有限区域以及无限区域，而且对于每一条无向边，拆出来的两个有向边的右侧区域可以拿来连边。

这样第一件事情就做完了。

接着就是点定位的过程了呢。

为了应对集训队作业中的强制在线的点定位，我使用了可持久化平衡树来解决问题。

首先是扫描线，那么在每两个相邻的$x$坐标之间都会有一些只可能在端点处相交的线段。

对于每条$x$坐标增大的有向边，我们都分别在两个$x$坐标处记录一个事件，一个为插入，另一个是删除。

我们用平衡树来维护这些线段，关键字为$x=\frac{x_l+x_r}{2}$时的$y$坐标。

顺次扫描的过程中只需要利用平衡树维护这些线段就行了。

对于定位点$(x,y)$：

我们找到包含了$x$坐标的那一个版本的平衡树，去查询线段的后继，即最下面的线段使得对于当前的$x$，$y$坐标大于查询的$y$。

若不存在后继，显然是无限区域。

否则返回这条线段的右侧区域。

这样的话就结束了呢。

时间复杂度$O(mlogm+qlogn)$。

有一些细节请参考代码。

经过了多次调♂戏之后终于是过了。。。

如果有疑问的话去参考我在UOJ上的交题记录好了。上面有几组丧心病狂的小数据。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;

typedef double db;
typedef long long ll;
typedef pair<db,int> pdi;
#define mp make_pair

#define N 100010
int n,m,_n,mxid,x[N],y[N],be[N<<1],en[N<<1],c[N],l[N<<1],r[N<<1],Right[N<<1];
bool del[N<<1];
vector<pdi>s[N];
map<int,int>M[N];

int getrev(int x){
	return (x&1)?x+1:x-1;
}
ll cross(int a,int b){
	return (ll)x[a]*y[b]-(ll)x[b]*y[a];
}

struct Edge{
	int u,v,l;
	Edge(){}
	Edge(int _u,int _v,int _l):u(_u),v(_v),l(_l){}
	
	bool operator<(const Edge&B)const{
		return l<B.l;
	}
}E[N];

#define inf 0x3f3f3f3f
struct Tree{
	int head[N],next[N<<1],end[N<<1],w[N<<1];
	void addedge(int a,int b,int c){
		static int q=1;
		end[q]=b;
		next[q]=head[a];
		w[q]=c;
		head[a]=q++;
	}
	void make(int a,int b,int c){
		addedge(a,b,c);
		addedge(b,a,c);
	}
	
	int dep[N],pa[N][21],mx[N][21];
	void dfs(int x,int fa){
		for(int j=head[x];j;j=next[j]){
			if(end[j]!=fa){
				dep[end[j]]=dep[x]+1;
				pa[end[j]][0]=x;
				mx[end[j]][0]=w[j];
				dfs(end[j],x);
			}
		}
	}
	void init(int n){
		for(int i=1;i<=n;++i){
			if(!dep[i]){
				dep[i]=1;
				dfs(i,-1);
			}
		}
		for(int j=1;j<=20;++j)
			for(int i=1;i<=n;++i){
				pa[i][j]=pa[pa[i][j-1]][j-1];
				mx[i][j]=max(mx[i][j-1],mx[pa[i][j-1]][j-1]);
			}
	}
	
	int query(int x,int y){
		if(dep[x]<dep[y])
			swap(x,y);
		int ans=-0x3f3f3f3f;
		for(int i=20;i>=0;--i)
			if(dep[pa[x][i]]>=dep[y])
				ans=max(ans,mx[x][i]),x=pa[x][i];
		if(x==y)
			return ans;
		for(int i=20;i>=0;--i)
			if(pa[x][i]!=pa[y][i]){
				ans=max(ans,mx[x][i]);
				x=pa[x][i];
				ans=max(ans,mx[y][i]);
				y=pa[y][i];
			}
		ans=max(ans,mx[x][0]);
		ans=max(ans,mx[y][0]);
		return ans;
	}
}T;

namespace Union_Set{
	int r[N],siz[N];
	void init(int n){
		for(int i=1;i<=n;++i)
			r[i]=i,siz[i]=1;
	}
	int find(int x){
		int q=x,rq;
		for(;x!=r[x];x=r[x]);
		for(;q!=x;rq=r[q],r[q]=x,q=rq);
		return x;
	}
	void merge(int x,int y){
		if(siz[x]>siz[y])
			swap(x,y);
		siz[y]+=siz[x];
		r[x]=y;
	}
}

#define ls ch[0]
#define rs ch[1]
struct Node{
	Node*ch[2];
	int id,p,siz;
	Node():siz(0){}
}mem[(N<<1)*40],*P=mem,Tnull,*null=&Tnull;
Node*newnode(){
	P->p=rand();
	P->siz=1;
	P->ch[0]=P->ch[1]=null;
	return P++;
}
void up(Node*p){
	p->siz=p->ls->siz+p->rs->siz+1;
}
void copy(Node*&p,Node*q){
	if(q==null)
		p=null;
	else
		*(p=newnode())=*q;
}
void merge(Node*&re,Node*p,Node*q){
	if(p==null)
		copy(re,q);
	else if(q==null)
		copy(re,p);
	else if(p->p<q->p){
		copy(re,p);
		merge(re->rs,p->rs,q);
		up(re);
	}
	else{
		copy(re,q);
		merge(re->ls,p,q->ls);
		up(re);
	}
}
void split(Node*re,int k,Node*&p,Node*&q){
	if(k==0){
		copy(p,null);
		copy(q,re);
	}
	else if(k==re->siz){
		copy(p,re);
		copy(q,null);
	}
	else if(k<=re->ls->siz){
		copy(q,re);
		split(re->ls,k,p,q->ls);
		up(q);
	}
	else{
		copy(p,re);
		split(re->rs,k-re->ls->siz-1,p->rs,q);
		up(p);
	}
}
db gety(int id,db _x){
	return y[be[id]]+(db)(y[en[id]]-y[be[id]])/(x[en[id]]-x[be[id]])*(_x-x[be[id]]);
}
bool check(int id,db _x,db _y){
	return _y<gety(id,_x)?0:1;
}
int calc_geq(Node*p,db _x,db _y){
	if(p==null)
		return 0;
	bool d=check(p->id,_x,_y);
	if(d==0)
		return p->rs->siz+1+calc_geq(p->ls,_x,_y);
	else
		return calc_geq(p->rs,_x,_y);
}
Node*succ(Node*p,db _x,db _y){
	if(p==null)
		return null;
	bool d=check(p->id,_x,_y);
	if(d==0){
		Node*re=succ(p->ls,_x,_y);
		return re==null?p:re;
	}
	else
		return succ(p->rs,_x,_y);
}
int getrank(Node*p,db _x,int id){
	if(p==null)
		return 0;
	if(p->id==id)
		return p->ls->siz;
	bool d=check(p->id,_x,gety(id,_x));
	if(d==0)
		return getrank(p->ls,_x,id);
	else
		return p->ls->siz+1+getrank(p->rs,_x,id);
}
Node*insert(Node*last,db _x,int id){
	int ans=calc_geq(last,_x,gety(id,_x));
	Node*p1,*p2,*re;
	split(last,last->siz-ans,p1,p2);
	Node*now=newnode();
	now->id=id;
	merge(re,p1,now);
	merge(re,re,p2);
	return re;
}
Node*cutdown(Node*last,db _x,int id){
	int ans=getrank(last,_x,id);
	Node*p1,*p2,*p3,*re;
	split(last,ans,p1,p2);
	split(p2,1,p2,p3);
	merge(re,p1,p3);
	return re;
}

int hx[N];
vector<int>quel[N],quer[N];

Node*root[N];

int getarea(db _x,db _y){
	if(_x<hx[1]||_x>hx[_n])
		return -1;
	int ins=lower_bound(hx+1,hx+_n+1,_x)-hx;
	if(ins!=1)
		--ins;
	Node*re=succ(root[ins],_x,_y);
	if(re==null)
		return -1;
	if(Right[re->id]==mxid)
		return -1;
	return Right[re->id];
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
	//freopen("tt.out","w",stdout);
#endif
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%d%d",&x[i],&y[i]);
	int a,b;
	for(i=1;i<=m;++i){
		scanf("%d%d%d",&a,&b,&c[i]);
		be[2*i-1]=a,en[2*i-1]=b;
		s[a].push_back(mp(atan2(y[b]-y[a],x[b]-x[a]),2*i-1));
		be[2*i]=b,en[2*i]=a;
		s[b].push_back(mp(atan2(y[a]-y[b],x[a]-x[b]),2*i));
	}
	
	for(i=1;i<=n;++i){
		sort(s[i].begin(),s[i].end());
		for(j=0;j<s[i].size();++j)
			M[i][s[i][j].second]=j;
	}
	
	for(i=1;i<=(m<<1);++i){
		l[i]=i-1;
		r[i]=i+1;
	}
	l[1]=0,r[m<<1]=m<<1^1;
	r[0]=1;
	
	int cnt=0,be_point,now_edge,id;
	ll area,mx_area=-1ll<<62;
	while(r[0]<=(m<<1)){
		++cnt;
		//printf("Area#%d\n",cnt);
		area=0;
		now_edge=r[0];
		be_point=be[now_edge];
		while(1){
			//printf("%d %d\n",x[be[now_edge]],y[be[now_edge]]);
			l[r[now_edge]]=l[now_edge];
			r[l[now_edge]]=r[now_edge];
			del[now_edge]=1;
			Right[now_edge]=cnt;
			area+=cross(be[now_edge],en[now_edge]);
			//if(en[now_edge]==be_point)
				//break;
			id=M[en[now_edge]][getrev(now_edge)];
			now_edge=s[en[now_edge]][(id+1)%s[en[now_edge]].size()].second;
			if(del[now_edge])
				break;
		}
		//printf("%lld\n",area);
		if(mx_area<area){
			mx_area=area;
			mxid=cnt;
		}
	}
	
	for(i=1;i<=m;++i)
		if(Right[2*i-1]!=mxid&&Right[2*i]!=mxid)
			E[i]=Edge(Right[2*i-1],Right[2*i],c[i]);
	
	sort(E+1,E+m+1);
	
	using namespace Union_Set;
	Union_Set::init(cnt);
	
	int rx,ry;
	for(i=1;i<=m;++i){
		rx=Union_Set::find(E[i].u);
		ry=Union_Set::find(E[i].v);
		if(rx!=ry){
			T.make(E[i].u,E[i].v,E[i].l);
			//printf("%d %d %d\n",E[i].u,E[i].v,E[i].l);
			Union_Set::merge(rx,ry);
		}
	}
	
	T.init(cnt);
	
	for(i=1;i<=n;++i)
		hx[i]=x[i];
	sort(hx+1,hx+n+1);
	_n=unique(hx+1,hx+n+1)-hx-1;
	
	int x1,x2;
	for(i=1;i<=(m<<1);++i)
		if(x[be[i]]<x[en[i]]){
			x1=lower_bound(hx+1,hx+_n+1,x[be[i]])-hx;
			x2=lower_bound(hx+1,hx+_n+1,x[en[i]])-hx;
			quel[x1].push_back(i);
			quer[x2].push_back(i);
		}
	
	for(root[0]=null,i=1;i<_n;++i){
		root[i]=root[i-1];
		if(i>1)
			for(j=0;j<quer[i].size();++j)
				root[i]=cutdown(root[i],(hx[i-1]+hx[i])*.5,quer[i][j]);
		for(j=0;j<quel[i].size();++j)
			root[i]=insert(root[i],(hx[i]+hx[i+1])*.5,quel[i][j]);
	}
	
	//fclose(stdin);

	int q;
	scanf("%d",&q);
	db x,y;
	int u,v;
	while(q--){
		scanf("%lf%lf",&x,&y);
		u=getarea(x,y);
		scanf("%lf%lf",&x,&y);
		v=getarea(x,y);
		if(u==-1||v==-1||Union_Set::find(u)!=Union_Set::find(v))
			puts("-1");
		else if(u==v)
			puts("0");
		else
			printf("%d\n",T.query(u,v));
	}
	
	return 0;
}