AOJ 2316: 人魚の魔女
この記事は、AOJ-ICPC Advent Calendarの記事です。
右下の点を軸にして線分を転がすのを実際にシミュレートしていきます。次のケースに嵌りました。
・とがっているケースでは、反対側の頂点が次の軸になるような場合がある。
・↑のケースにおいては、x座標が1より遠いところに行く可能性があり、2つ先の辺を見る必要がでてくる。
・↑↑のケースにおいて、ぶつかる場所までに必要な角度は45度ふえる。45°=π/4 (rad)である。
久しぶりに幾何問題で嵌ったので、反省をしています。
#include<stdio.h> #include<vector> #include<algorithm> #include<math.h> using namespace std; const long double EPS = 1e-13; const long double INF = 1e+10; const long double PI = acos(-1); Pt p[50]; char ans[4][10]={"Red","Green","Blue","White"}; int main(){ int a; long double b,c; scanf("%d%Lf%Lf",&a,&b,&c); for(int i=0;i<a;i++){ int x,y; scanf("%d%d",&x,&y); p[i]=Pt((long double)x,(long double)y); } int cnt=0; Pt st=(p[0]*(p[1].x-b)+p[1]*(b-p[0].x))/(p[1].x-p[0].x); Pt now=st+(p[1]-p[0])/((p[1]-p[0]).ABS()); //printf("%Lf %Lf %Lf\n",st.x,st.y,dSP(p[0],p[1],st)); //printf("%Lf %Lf %Lf\n",now.x,now.y,dSP(p[0],p[1],st)); int at=0; Pt last=st; while(1){ int tc=cnt+1; int ta=at; Pt tp; long double th=-9999999; if(at<a-2&&iCS(now,1.0L,p[at+1],p[at+2])){ pair<Pt,Pt> it=pCL(now,1.0L,p[at+1],p[at+2]); if(iSP(p[at+1],it.first,p[at+2])==2||(it.first-p[at+2]).ABS()<EPS){ if(th<(it.first-now).arg()){ tp=it.first; th=(it.first-now).arg(); ta=at+1; tc=cnt+1; } } if(iSP(p[at+1],it.second,p[at+2])==2||(it.second-p[at+2]).ABS()<EPS){ if(th<(it.second-now).arg()){ tp=it.second; th=(it.second-now).arg(); ta=at+1; tc=cnt+1; } } } if(at<a-2&&iCS(now,sqrt(2.0L),p[at+1],p[at+2])){ pair<Pt,Pt> it=pCL(now,sqrt(2.0L),p[at+1],p[at+2]); if(iSP(p[at+1],it.first,p[at+2])==2||(it.first-p[at+2]).ABS()<EPS){ // printf("%Lf ",(it.first-now).arg()); if(th<(it.first-now).arg()-PI/4){ tp=it.first; th=(it.first-now).arg()-PI/4; ta=at+1; tc=cnt+2; } } if(iSP(p[at+1],it.second,p[at+2])==2||(it.second-p[at+2]).ABS()<EPS){ // printf("%Lf\n",(it.second-now).arg()); if(th<(it.second-now).arg()-PI/4){ tp=it.second; th=(it.second-now).arg()-PI/4; ta=at+1; tc=cnt+2; } } } if(at<a-3&&iCS(now,sqrt(2.0L),p[at+2],p[at+3])){ pair<Pt,Pt> it=pCL(now,sqrt(2.0L),p[at+2],p[at+3]); if(iSP(p[at+2],it.first,p[at+3])==2||(it.first-p[at+3]).ABS()<EPS){ // printf("%Lf ",(it.first-now).arg()); if(th<(it.first-now).arg()-PI/4){ tp=it.first; th=(it.first-now).arg()-PI/4; ta=at+2; tc=cnt+2; } } if(iSP(p[at+2],it.second,p[at+3])==2||(it.second-p[at+3]).ABS()<EPS){ // printf("%Lf\n",(it.second-now).arg()); if(th<(it.second-now).arg()-PI/4){ tp=it.second; th=(it.second-now).arg()-PI/4; ta=at+2; tc=cnt+2; } } } { pair<Pt,Pt> it=pCL(now,1.0L,now,p[at+1]); if(iSP(now,it.first,p[at+1])==2||(it.first-p[at+1]).ABS()<EPS){ if(th<(it.first-now).arg()){ th=(it.first-now).arg(); tp=it.first; ta=at;tc=cnt+1; } } if(iSP(now,it.second,p[at+1])==2||(it.second-p[at+1]).ABS()<EPS){ if(th<(it.second-now).arg()){ th=(it.second-now).arg(); tp=it.second; ta=at;tc=cnt+1; } } } cnt=tc; now=tp; at=ta; //printf("%Lf\n",th); //printf("%Lf %Lf %Lf %Lf %Lf %d %d\n",th,now.x,now.y,dSP(p[0],p[1],now),dSP(p[1],p[2],now),at,cnt); if(now.x>c){ break; } } //printf("%d\n",cnt); printf("%s\n",ans[cnt%4]); }