tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 1279: Geometric Map

英語を読むだけ。*1
1145148108931919364回くらい誤読すると自然とコードが汚くなる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
using namespace std;
int G[510][510];
int L[510][510];
int x[510];
int y[510];
int cnt[510];
vector<int>g[510];
double ijk[510];
int v[510];
int rev[510];
int ans[510];
int tc[510];
int p[510];
int q[510];
int r[510];
int s[510];
int ABS(int a){return max(a,-a);}
int dcalc(int a,int b,int c,int d){
	return (x[b]-x[a])*(x[d]-x[c])+(y[b]-y[a])*(y[d]-y[c]);
}
double dist(int a,int b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int ccw(int a,int b,int c,int d,int e,int f){
	int X1=c-a;int X2=e-a;
	int Y1=d-b;int Y2=f-b;
	if(X1*Y2!=Y1*X2)return 0;
	if(X1*X2<0)return 0;
	if(Y1*Y2<0)return 0;
	if(ABS(X1)<ABS(X2))return 0;
	if(ABS(Y1)<ABS(Y2))return 0;
	return 1;
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		int sx,sy,gx,gy;
		scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
		int sz=0;
		map<pair<int,int>,int> m;
		for(int i=0;i<510;i++)g[i].clear();
		for(int i=0;i<510;i++)tc[i]=0;
		for(int i=0;i<510;i++)cnt[i]=0;
		for(int i=0;i<510;i++)for(int j=0;j<510;j++){
			G[i][j]=0;
			L[i][j]=-1;
		}
		for(int i=0;i<a;i++){
			scanf("%d%d%d%d",p+i,q+i,r+i,s+i);
			int from=-1;
			int to=-1;
			if(m.count(make_pair(p[i],q[i]))){
				from=m[make_pair(p[i],q[i])];
			}else{
				m[make_pair(p[i],q[i])]=sz;
				x[sz]=p[i];y[sz]=q[i];
				from=sz++;
			}
			if(m.count(make_pair(r[i],s[i]))){
				to=m[make_pair(r[i],s[i])];
			}else{
				m[make_pair(r[i],s[i])]=sz;
				x[sz]=r[i];y[sz]=s[i];
				to=sz++;
			}
		}
		for(int i=0;i<a;i++){
			vector<pair<double,int> > o;
			int ss=m[make_pair(p[i],q[i])];
			for(int j=0;j<sz;j++){
				if(ccw(p[i],q[i],r[i],s[i],x[j],y[j])){
					o.push_back(make_pair(dist(ss,j),j));
				}
			}
			std::sort(o.begin(),o.end());
			for(int j=0;j<o.size()-1;j++){
				int E=o[j].second;
				int F=o[j+1].second;
				G[E][F]=G[F][E]=1;
				cnt[E]++;
				cnt[F]++;
			}
		}
	/*	for(int i=0;i<sz;i++){
			if(x[i]==364&&y[i]==0){
				for(int j=0;j<sz;j++)if(G[i][j])printf("%d %d\n",x[j],y[j]);
			}
		}*/
		for(int i=0;i<sz;i++){
			if(cnt[i]==1){
				for(int j=0;j<sz;j++)if(G[i][j]){
					vector<int>t;
					vector<int>u;
					int rem=0;
					for(int k=0;k<sz;k++){
						if(G[j][k]&&cnt[k]!=1)t.push_back(k);
						else if(G[j][k])u.push_back(k);
					}
				//	printf("%d,%d: %d\n",x[i],y[i],t.size());
				//	G[i][j]=G[j][i]=0;
					G[j][t[0]]=G[t[0]][j]=0;
					G[j][t[1]]=G[t[1]][j]=0;
					G[t[0]][t[1]]=G[t[1]][t[0]]=1;
					L[t[0]][t[1]]=L[t[0]][j];
					if(~L[t[0]][t[1]]&&~L[j][t[1]])L[t[0]][t[1]]&=L[j][t[1]];
					else if(!~L[t[0]][t[1]])L[t[0]][t[1]]=L[j][t[1]];
					L[t[1]][t[0]]=L[j][t[0]];
					if(~L[t[1]][t[0]]&&~L[t[1]][j])L[t[1]][t[0]]&=L[t[1]][j];
					else if(!~L[t[1]][t[0]])L[t[1]][t[0]]=L[t[1]][j];
					for(int k=0;k<u.size();k++){
					G[j][u[k]]=G[u[k]][j]=0;
					int dot=dcalc(t[0],t[1],j,u[k]);
					if(dot>0){
						//L[t[1]][t[0]]=1;
						L[t[0]][t[1]]=0;
					}else if(dot==0){
						L[t[0]][t[1]]=L[t[1]][t[0]]=0;
					}else{
						//L[t[0]][t[1]]=1;
						L[t[1]][t[0]]=0;
					}
					}
				}
			}
		}
		for(int i=0;i<sz;i++)for(int j=0;j<sz;j++){
			if(G[i][j]&&L[i][j]!=0){
				g[i].push_back(j);
//			if(x[i]==9||x[j]==9)printf("%d,%d %d,%d\n",x[i],y[i],x[j],y[j]);
			}
		}
		int S=m[make_pair(sx,sy)];
		int T=m[make_pair(gx,gy)];
		for(int i=0;i<sz;i++){
			ijk[i]=99999999;
			v[i]=0;
			rev[i]=-1;
		}
		priority_queue<pair<double,int> >Q;
		ijk[S]=0;
		Q.push(make_pair(0.0,S));
		while(Q.size()){
			double cost=-Q.top().first;
			int at=Q.top().second;
			Q.pop();
			if(v[at])continue;
			v[at]=1;
			for(int i=0;i<g[at].size();i++){
				if(!v[g[at][i]]&&ijk[g[at][i]]>cost+dist(at,g[at][i])){
					ijk[g[at][i]]=cost+dist(at,g[at][i]);
					rev[g[at][i]]=at;
					Q.push(make_pair(-ijk[g[at][i]],g[at][i]));
				}
			}
		}
		if(ijk[T]>9999999){
			printf("-1\n");continue;
		}
		int ind=0;
		int now=T;
		while(now!=S){
			ans[ind++]=now;
			now=rev[now];
		}
		ans[ind++]=S;
		for(int i=ind-1;i>=0;i--){
			printf("%d %d\n",x[ans[i]],y[ans[i]]);
		}
		printf("0\n");
	}
}

*1:日本語で問題概要を書いてあるブログを見たんだけど、そこは説明不十分すぎたし、英語が難しすぎる。