tozangezan's diary

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

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]);
}