AOJ 1352: Cornering at Poles

中心を移動させる一般的なテクにより、円が障害物で点が動く問題となる。
円と円の交点、点たちからの接線、円と円の共通接線を求めて最短路。移動可能性が本質。

sAPの仕様がよく分からなくて時間を無駄に使った。本当に練習不足である。

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);

vector<Pt> hb;
Pt c[10];
double ijk[11000];
int v[11000];
int main(){
	int a,gx,gy;
	scanf("%d%d%d",&a,&gx,&gy);
	Pt g=Pt((double)gx,(double)gy);
	hb.push_back(Pt(0,0));
	hb.push_back(g);
	for(int i=0;i<a;i++){
		double x,y;
		scanf("%lf%lf",&x,&y);
		c[i]=Pt(x,y);
	}
	for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
		if((c[i]-c[j]).ABS()<200.0){
			pair<Pt,Pt> it=pCC(c[i],100.0,c[j],100.0);
			hb.push_back(it.first);
			hb.push_back(it.second);
		}
	}
	int rn=hb.size();
	for(int i=0;i<rn;i++){
		for(int j=0;j<a;j++){
			if((hb[i]-c[j]).ABS()>100.0+EPS){
				pair<Pt,Pt> it=tCP(c[j],100.0,hb[i]);
				hb.push_back(it.first);
				hb.push_back(it.second);
			}
		}
	}
	for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
		Pt v=(c[j]-c[i])*100.0/((c[j]-c[i]).ABS())*Pt(0,1);
		hb.push_back(c[i]+v);
		hb.push_back(c[i]-v);
		hb.push_back(c[j]+v);
		hb.push_back(c[j]-v);
		if((c[i]-c[j]).ABS()>200.0){
			double th=asin(200.0/(c[i]-c[j]).ABS());
			hb.push_back(c[i]+v*Pt(cos(-th),sin(-th)));
			hb.push_back(c[i]-v*Pt(cos(th),sin(th)));
			hb.push_back(c[j]+v*Pt(cos(th),sin(th)));
			hb.push_back(c[j]-v*Pt(cos(-th),sin(-th)));
		}
	}
	int n=hb.size();
	for(int i=1;i<n;i++){
		ijk[i]=999999999.9;
	}
	for(int i=0;i<n;i++){
		double dist=9999999999.9;
		int at=0;
		for(int j=0;j<n;j++){
			if(!v[j]&&dist>ijk[j]){
				dist=ijk[j];at=j;
			}
		}
		v[at]=1;
		for(int j=0;j<n;j++){
			if(v[j]||ijk[j]<ijk[at]+(hb[at]-hb[j]).ABS())continue;
			bool ok=true;
			for(int k=0;k<a;k++){
				if(dSP(hb[at],hb[j],c[k])<100.0-EPS)ok=false;
			}
			if(ok){
				ijk[j]=ijk[at]+(hb[at]-hb[j]).ABS();
			}
		}
		int on=0;
		for(int j=0;j<a;j++){
			if(100.0-EPS<(c[j]-hb[at]).ABS()&&(c[j]-hb[at]).ABS()<100.0+EPS)on+=(1<<j);
		}
		for(int j=0;j<n;j++){
			if(v[j])continue;
			for(int k=0;k<a;k++){
				if(!(on&(1<<k)))continue;
				if(100.0-EPS>(c[k]-hb[j]).ABS()||(c[k]-hb[j]).ABS()>100.0+EPS)continue;
				bool ok1=true;
				bool ok2=true;
				for(int l=0;l<a;l++){
					if(k==l)continue;
					if((c[k]-c[l]).ABS()>200.0)continue;
					pair<Pt,Pt> tmp=pCC(c[k],100.0,c[l],100.0);
					if(sAP(hb[at]-c[k],hb[j]-c[k],tmp.first-c[k])>0)ok1=false;
					if(sAP(hb[j]-c[k],hb[at]-c[k],tmp.first-c[k])>0)ok2=false;
					if(sAP(hb[at]-c[k],hb[j]-c[k],tmp.second-c[k])>0)ok1=false;
					if(sAP(hb[j]-c[k],hb[at]-c[k],tmp.second-c[k])>0)ok2=false;
				//	if(i==1&&j==70&&l==1)printf("%f %f %f\n",(hb[at]-c[k]).arg(),(hb[j]-c[k]).arg(),(tmp.first-c[k]).arg());
				}
				
				if(ok1){
					double th=(hb[j]-c[k]).arg()-(hb[at]-c[k]).arg();
					if(th<0)th+=PI*2;
					Pt chk=c[k]+(hb[at]-c[k])*Pt(cos(th/2),sin(th/2));
					bool ok=true;
					for(int l=0;l<a;l++)if((chk-c[l]).ABS()<100.0-EPS)ok=false;
					if(ok){
			//			if(i==1)printf("%d (%f, %f) %d 1\n",at,hb[j].x,hb[j].y,k);
						ijk[j]=min(ijk[j],ijk[at]+100.0*th);
					}
				}
				if(ok2){
					double th=(hb[at]-c[k]).arg()-(hb[j]-c[k]).arg();
					if(th<0)th+=PI*2;
					Pt chk=c[k]+(hb[j]-c[k])*Pt(cos(th/2),sin(th/2));
					bool ok=true;
					for(int l=0;l<a;l++)if((chk-c[l]).ABS()<100.0-EPS)ok=false;
					if(ok){
				//		if(i==1)printf("%d (%f, %f) %d 2\n",at,hb[j].x,hb[j].y,k);
						ijk[j]=min(ijk[j],ijk[at]+100.0*th);
					}
				}
			}
		}
	//	if(i==1)for(int j=0;j<hb.size();j++)printf("(%f, %f): %f\n",hb[j].x,hb[j].y,ijk[j]);	
	}
	//for(int i=0;i<hb.size();i++)printf("(%f, %f): %f\n",hb[i].x,hb[i].y,ijk[i]);
	if(ijk[1]<99999999.9)printf("%.12f\n",ijk[1]);
	else printf("0.0\n");
}