tozangezan's diary

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

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