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