AOJ 1151: くるくる
ブログに記事を書きます Advent Calendar 2014 - Adventarの11日目の記事です。
回すだけ。まわしましょう。あと、180度系は面倒なので最初に座標を回しましょう。あとで戻しましょう。
あんまり実装の仕方がよくなくてepsを2種類使う羽目になった。
#include<stdio.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; double EPS2=1e-6; Pt p[110]; int n; int main(){ double L,R; int a; while(scanf("%lf%lf%d",&L,&R,&a),a){ R*=PI*2; n=a; for(int i=0;i<a;i++){ double x,y; scanf("%lf%lf",&x,&y); p[i]=Pt(x,y); } p[a]=p[0]; for(int i=0;i<=a;i++)p[i]=p[i]*Pt(cos(1),sin(1)); Pt s=Pt(0,0); Pt t=Pt(0,L)*Pt(cos(1),sin(1)); Pt c=s; double d=(s-t).arg(); int last=0; while(1){ Pt vs=s-c; double sr=vs.ABS(); Pt vt=t-c; double tr=vt.ABS(); double val=9999999; Pt to=Pt(0,0); vector<Pt>e; for(int i=0;i<a;i++){ if(sig((p[i]-c).ABS())&&(p[i]-c).ABS()<sr){ e.push_back(p[i]); } if(iCS(c,sr,p[i],p[(i+1)%a])){ pair<Pt,Pt> t1=pCL(c,sr,p[i],p[(i+1)%a]); //printf("%f %f, %f %f\n",t1.first.x,t1.first.y,t1.second.x,t1.second.y); double lb=0; double rb=(p[i+1]-p[i]).ABS(); if((p[i]-t1.first).dot(p[i+1]-t1.first)<=EPS)e.push_back(t1.first); if((p[i]-t1.second).dot(p[i+1]-t1.second)<=EPS)e.push_back(t1.second); } } for(int i=0;i<e.size();i++){ Pt pe=e[i]*Pt(cos(-1),sin(-1)); // printf("%f %f\n",pe.x,pe.y); if(!sig(sr))continue; // if((e[i]-c).ABS()<sr){ if(sig((e[i]-c).ABS())){ double th=(e[i]-c).arg(); if(!sig(th-d)){ Pt tmp=c+(e[i]-c)*Pt(cos(EPS2),-sin(EPS2)); bool out=false; if(sGP(tmp)==-1)out=true; for(int j=0;j<a;j++)if(iSSstrict(c,tmp,p[j],p[j+1])){out=true;} if(out){ th=d; }else th=d-PI*2; }else if(th>d)th-=PI*2; if(val>d-th||(val+EPS>d-th&&(e[i]-c).ABS()>(to-c).ABS())){ to=e[i]; val=d-th; } // printf("%f, %f: %f %f\n",e[i].x,e[i].y,th,val); } // } } e.clear(); for(int i=0;i<a;i++){ if(sig((p[i]-c).ABS())&&(p[i]-c).ABS()<tr){ e.push_back(p[i]); } if(iCS(c,tr,p[i],p[(i+1)%a])){ pair<Pt,Pt> t1=pCL(c,tr,p[i],p[(i+1)%a]); if((p[i]-t1.first).dot(p[i+1]-t1.first)<=EPS)e.push_back(t1.first); if((p[i]-t1.second).dot(p[i+1]-t1.second)<=EPS)e.push_back(t1.second); } } double d2=d+PI; if(d2>=PI)d2-=PI*2; for(int i=0;i<e.size();i++){ if(!sig(tr))continue; // if((e[i]-c).ABS()<tr){ if(sig((e[i]-c).ABS())){ double th=(e[i]-c).arg(); if(!sig(th-d2)){ Pt tmp=c+(e[i]-c)*Pt(cos(EPS2),-sin(EPS2)); bool out=false; if(sGP(tmp)==-1)out=true; for(int j=0;j<a;j++)if(iSSstrict(c,tmp,p[j],p[j+1])){out=true;} if(out){ th=d2; }else th=d2-PI*2; }else if(th>d2)th-=PI*2; if(val>d2-th||(val+EPS>d2-th&&(e[i]-c).ABS()>(to-c).ABS())){ to=e[i]; val=d2-th; } // printf("%f, %f: %f %f\n",e[i].x,e[i].y,th,val); } // } } if(val>R){ val=R; } if(sig(val))last=0; last++; if(last>110)break; vs=vs*Pt(cos(val),-sin(val)); vt=vt*Pt(cos(val),-sin(val)); d-=val; if(d<=-PI)d+=2*PI; s=c+vs; t=c+vt; c=to; Pt ps=s*Pt(cos(-1),sin(-1)); Pt pt=t*Pt(cos(-1),sin(-1)); Pt pc=c*Pt(cos(-1),sin(-1)); // printf("(%f, %f) (%f, %f): %f (%f, %f)\n",ps.x,ps.y,pt.x,pt.y,val,pc.x,pc.y); R-=val; if(sig(R)!=1)break; } s=s*Pt(cos(-1),sin(-1)); printf("%.12f %.12f\n",s.x,s.y); } }