考场程序1

gistfile1.cpp

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#define REP(i,n) for(int i=0;i<n;++i)
#define CLR(x,c) memset(x,c,sizeof x)
#define SHOW_MEMORY(x) cout<<sizeof(x)/(1024*1024.0)<<"MB"

//todo : brute force check
using namespace std;

void setIO(string a){
	string in=a+".in",out=a+".out";
	freopen(in.c_str(),"r",stdin);
	freopen(out.c_str(),"w",stdout);
}

const int MAX_N=int(1e5)+10;

const int MAX_F=MAX_N*3;

typedef long long int64;

struct P{
	int x,y;
	P(int x=0,int y=0):x(x),y(y){}
	P operator+(P o){return P(x+o.x,y+o.y);}
	P operator-(P o){return P(x-o.x,y-o.y);}
	int64 operator*(P o){return 1LL*x*o.x+1LL*y*o.y;}
	int64 operator^(P o){return 1LL*x*o.y-1LL*y*o.x;}
	double al(){return atan2(y,x);}
	double abs(){return hypot(x,y);}
	void read(){scanf("%d%d",&x,&y);x*=2,y*=2;} //*2
	bool operator==(const P&o)const{
		return x==o.x&&y==o.y;
	}
};

//replace alpha with det if posssible :)

int sign(int64 x){
	return x<0?-1:x>0;
}

int64 cross(P p1,P p2,P p3){return (p2-p1)^(p3-p1);}

int crossOp(P p1,P p2,P p3){return sign(cross(p1,p2,p3));}

int n,m,nQ;
P ps[MAX_N];

struct Edge;

vector<Edge*> allE;

struct Edge{
	Edge*rev,*nxt,*pre;
	double alpha;
	int sta,tar;
	int cst;
	
	int id;
	
	Edge(int sta,int tar,int cst):sta(sta),tar(tar),cst(cst),id(-1){
		alpha=(ps[tar]-ps[sta]).al();
		allE.push_back(this);
	}
};

vector<Edge*> es[MAX_N];

Edge* makeEdge(int u,int v,int c){
	Edge*e=new Edge(u,v,c);
	es[u].push_back(e);
	return e;
}

void addEdge(int u,int v,int c){
	Edge*uv=makeEdge(u,v,c);
	Edge*vu=makeEdge(v,u,c);
	uv->rev=vu,vu->rev=uv;
}

void readInput(){
	cin>>n>>m;
	REP(i,n){
		ps[i].read();
	}
	REP(i,m){
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		--u,--v;
		addEdge(u,v,c);
	}
}

bool cmp(Edge*a,Edge*b){
	return a->alpha<b->alpha;
}

int nId;

int forbid;

void buildGraph(){
	//sort 
	REP(i,n){
		vector<Edge*>&arr=es[i];
		if(arr.empty())
			continue;
		sort(arr.begin(),arr.end(),cmp);
		REP(j,arr.size()){
			Edge*nxt;
			if(j+1<arr.size())
				nxt=arr[j+1];
			else
				nxt=arr[0];
			arr[j]->nxt=nxt;
			nxt->pre=arr[j];
		}
	}
	
	//build
	
	nId=0;
	REP(it,allE.size()){
		Edge*e=allE[it];
		if(e->id!=-1)
			continue;
			
		int64 area=0;	
			
		while(e->id==-1){
			area+=ps[e->sta]^ps[e->tar];
			e->id=nId;
			e=e->rev->pre;
		}
		
		if(area<0){
			forbid=nId;
		}
		
		nId++;		
	}
	
	//build MST
}

struct WEdge{
	int u,v,c;
	WEdge(int u,int v,int c):u(u),v(v),c(c){}
	bool operator<(const WEdge&o)const{
		return c<o.c;
	}
};

vector<WEdge> wes;

struct UF{
	int fa[MAX_F];
	void init(int n){
		REP(i,n)
			fa[i]=i;
	}
	
	int find(int i){
		return fa[i]==i?i:fa[i]=find(fa[i]);
	}
	
	bool unite(int a,int b){
		a=find(a),b=find(b);
		fa[a]=b;
		return a!=b;
	}
}uf;

struct Tree{
	static const int MAX_N=MAX_F,MAX_LOG=20;
	
	struct Edge{
		int t,c;
		Edge(int t,int c):t(t),c(c){}
	};
	
	vector<Edge> E[MAX_N];

	void addEdge(int u,int v,int c){
		E[u].push_back(Edge(v,c));
		E[v].push_back(Edge(u,c));			
	}
	
	int anc[MAX_N][MAX_LOG];
	
	int mx[MAX_N][MAX_LOG];
	
	int dep[MAX_N];
	
	int n;
	
	void init(int n){
		this->n=n;
	}
	
	void preprocess(int rt){
		queue<int> que;
		
		que.push(rt);
		CLR(anc[rt],-1);
		CLR(mx[rt],-1);
		dep[rt]=0;
		
		while(!que.empty()){
			int u=que.front();que.pop();
			for(vector<Edge>::iterator e=E[u].begin();e!=E[u].end();++e){
				if(e->t==anc[u][0])
					continue;
				int v=e->t;
				
				dep[v]=dep[u]+1;
				anc[v][0]=u;
				mx[v][0]=e->c;
				
				for(int i=0;i+1<MAX_LOG;++i){
					int go=anc[v][i];
					if(go==-1)
						anc[v][i+1]=-1,mx[v][i+1]=-1;
					else {
						anc[v][i+1]=anc[go][i];
						mx[v][i+1]=max(mx[v][i],mx[go][i]);
					}
				}
				que.push(v);
			}
		}
		
		
	}
	
	int query(int u,int v){
		int ans=-1;
		
		//make dep[u]>dep[v]
		if(dep[u]<dep[v])
			swap(u,v);
		
		int need=dep[u]-dep[v];
		REP(i,MAX_LOG)
			if(need>>i&1)
				ans=max(ans,mx[u][i]),u=anc[u][i];
		
		if(u==v)
			return ans;
		
		for(int i=MAX_LOG-1;i>=0;--i){
			if(anc[u][i]!=anc[v][i]){
				ans=max(ans,mx[u][i]);
				u=anc[u][i];
				
				ans=max(ans,mx[v][i]);
				v=anc[v][i];
			}
		}
		
		ans=max(ans,mx[u][0]);
		ans=max(ans,mx[v][0]);
		
		return ans;
	}
};

Tree tree;

void buildMST(){
	REP(it,allE.size()){
		Edge*e=allE[it];
		int u=e->id,v=e->rev->id;
		if(u==forbid||v==forbid)
			continue;
		wes.push_back(WEdge(u,v,e->cst));
	}
	
	sort(wes.begin(),wes.end());
	
	uf.init(nId);
	
	tree.init(nId);
	
	REP(it,wes.size()){
		WEdge&e=wes[it];
		if(uf.unite(e.u,e.v)){
			//cerr<<e.u<<" "<<e.v<<" "<<e.c<<endl;
			tree.addEdge(e.u,e.v,e.c);
		}
	}
	
	int rt=0;
	if(forbid==0)
		rt=1;
	
	tree.preprocess(rt);
}

const int ADD=0,QRY=1,DEL=2;

struct Event{
	int type;
	int x;
	Edge*e;//for add/del edge
	int y;//for query
	int*ptr;
	
	//query
	Event(int x,int y,int*ptr):x(x),y(y),type(QRY),ptr(ptr){}
	//add/del
	Event(int x,Edge*e,int type):x(x),e(e),type(type){}
};

bool operator<(const Event&a,const Event&b){
	if(a.x!=b.x)
		return a.x<b.x;
	//add->query->delete
	return a.type<b.type;
}

vector<Event> events;

const int PT=0,EG=1;

struct Stuff{
	int type;
	P p1,p2;
	int id;
	
	Stuff(P p):p1(p),type(PT){}
	
	Stuff(P p1,P p2):p1(p1),p2(p2),type(EG){}
};

//whether a is upper than b

bool checkIt(P p1,P p2,P q){
	return q.x>=p1.x&&q.x<=p2.x;
}

bool check(P p1,P p2,P q1,P q2){
	if(p2==q1){
		return true;
	}
	if(q2==p1){
		return false;
	}
	
	if(checkIt(p1,p2,q1)){
		int op=crossOp(p1,p2,q1);
		if(op!=0)
			return op<0;
	}
	
	if(checkIt(p1,p2,q2)){
		int op=crossOp(p1,p2,q2);
		if(op!=0)
			return op<0;
	}
	
	if(checkIt(q1,q2,p1)){
		int op=crossOp(q1,q2,p1);
		if(op!=0)
			return op>0;
	}
	
	if(checkIt(q1,q2,p2)){
		int op=crossOp(q1,q2,p2);
		if(op!=0)
			return op>0;
	}
	
	return false;
}

bool operator<(const Stuff&a,const Stuff&b){
	if(a.type==PT&&b.type==EG)
		return crossOp(b.p1,b.p2,a.p1)>0;
		
	if(a.type==EG&&b.type==PT)
		return !(b<a);
		
	if(a.type==EG&&b.type==EG){
		//if they only share a point , the righter one is smaller
		return check(a.p1,a.p2,b.p1,b.p2);
	}
}

struct Query{
	P p1,p2;
	int u,v;
	
	void rd(P&p){
		double x,y;
		scanf("%lf%lf",&x,&y);
		p.x=x*2+0.1;p.y=y*2+0.1;
	}
	
	void read(){
		rd(p1),rd(p2);
	}
};

Query qs[MAX_N];

void lineSweep(){
	//find every point's location
	
	//read queries
	
	cin>>nQ;
	
	REP(i,nQ){
		qs[i].read();
	}
	
	//make Events
	REP(it,allE.size()){
		Edge*e=allE[it];
		P p1=ps[e->sta],p2=ps[e->tar];
		
		if(p1.x<p2.x){
			//add Edge
			events.push_back(Event(p1.x,e,ADD));
			events.push_back(Event(p2.x,e,DEL));
		}
	}
	
	REP(i,nQ){
		Query&q=qs[i];
		events.push_back(Event(q.p1.x,q.p1.y,&q.u));
		events.push_back(Event(q.p2.x,q.p2.y,&q.v));
	}
	
	sort(events.begin(),events.end());
	
	set<Stuff> stf;
	
	REP(it,events.size()){
		Event&e=events[it];
		//cerr<<e.x<<endl;
		if(e.type==ADD){
			Edge*ep=e.e;
			Stuff st(ps[ep->sta],ps[ep->tar]);
			
			st.id=ep->id;
			stf.insert(st);
		} else if(e.type==DEL){
			Edge*ep=e.e;
			Stuff st(ps[ep->sta],ps[ep->tar]);
			
			st.id=ep->id;
			//cerr<<stf.size()<<"->";
			stf.erase(st);
			//cerr<<stf.size()<<endl;
		} else {
			//find the first one who > this :)
			Stuff st(P(e.x,e.y));
			set<Stuff>::iterator it=stf.lower_bound(st);
			if(it==stf.end()){
				*e.ptr=forbid;
			} else {
				*e.ptr=it->id;
			}
		}
	}
}

void answerQueries(){
	REP(i,nQ){
		Query&q=qs[i];
		//cout<<q.u<<" "<<q.v<<endl;
		if(q.u==forbid||q.v==forbid){
			puts("-1");
			continue;
		}
		if(q.u==q.v){
			puts("0");
			continue;
		}
		printf("%d\n",tree.query(q.u,q.v));
	}
}

void work(){
	buildGraph();
	buildMST();
	lineSweep();
	answerQueries();
}

int main(){	
	setIO("graph");
	readInput();
	work();
	return 0;
}