Problem: Example

Input

8 900 0
40 100
70 -80
350 30
680 -20
230 230
300 400
530 130
75 -275


Output

1210.99416

Solution (in CPP):

Solution:
#include<cstdio>
#include<complex>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

typedef double Real;
typedef complex<Real> Point;
typedef complex<Real> Vector;
typedef pair<Point,Point> Line;
typedef pair<Point,Point> Segment;

const Real eps=1e-9;
const Real PI=acos(-1.0);
const Real inf=1e9;

template<class T> bool eq(T a,T b){
	return abs(a-b)<eps;
}
template<class T> int sgn(T a){
	if(eq(a,0.0)) return 0;
	if(a>0) return 1;
	return -1;
}

inline Real normalize(Real theta){
	while(theta<-PI) theta+=PI*2;
	while(theta>PI) theta-=PI*2;
	return theta;
}
inline Real arg(Vector v){
	return atan2(v.imag(),v.real());
}

struct Circle{
	Point center;
	Real r;
	vector<Real> args;
	Circle(){}
	Circle(Point p,Real r):center(p),r(r){}
};

bool onSeg(Point a,Point b,Point c){
	return eq(abs(a-b),abs(a-c)+abs(c-b));
}

Real doP(Vector a,Vector b){
	return (conj(a)*b).real();
}

Vector proj(Vector p,Vector b){
	return b*doP(p,b)/norm(b);
}

bool iCS(Circle c,Segment s){
	Point p=s.first,q=s.second;
	Point h=p+proj(c.center-p,q-p);
	if(onSeg(p,q,h)){
		Real d=abs(h-c.center);
		return sgn(d-c.r)<0;
	}
	Real d=min(abs(p-c.center),abs(q-c.center));
	return sgn(d-c.r)<0;
}

bool cCP(Circle c,Point p){
	return sgn(c.r-abs(p-c.center))>0;
}

void iCC(Circle &c1,Circle c2){
	Real d=abs(c1.center-c2.center);
	Real r1=c1.r,r2=c2.r;
	if(sgn(d-r1-r2)>0) return;
	Real theta=arg(c2.center-c1.center);
	theta=normalize(theta);
	if(sgn(d-r1-r2)==0){
		c1.args.push_back(theta);
		return;
	}
	Real phi=acos((r1*r1+d*d-r2*r2)/(2.0*r1*d));
	c1.args.push_back(normalize(theta+phi));
	c1.args.push_back(normalize(theta-phi));
}

void tCP(Circle &c,Point p){
	if(cCP(c,p)) return;
	if(eq(abs(p-c.center),c.r)){
		Real theta=arg(p-c.center);
		c.args.push_back(theta);
	}
	Real d=abs(p-c.center);
	Real r=c.r;
	Real theta=arg(p-c.center);
	Real phi=acos(r/d);
	c.args.push_back(normalize(theta+phi));
	c.args.push_back(normalize(theta-phi));
}

void otCC(Circle &c1,Circle c2){
	//存在しないときを考えてない 
	//中心が一致するときを考えてない 
	Real theta=arg(c2.center-c1.center);
	Real d=abs(c1.center-c2.center);
	Real phi=acos((c1.r-c2.r)/d);
	c1.args.push_back(normalize(theta+phi));
	c1.args.push_back(normalize(theta-phi));
}

void itCC(Circle &c1,Circle c2){
	Real d=abs(c1.center-c2.center);
	Real theta=arg(c2.center-c1.center);
	Real r1=c1.r,r2=c2.r;
	if(sgn(r1+r2-d)>0){//intersect
		return ;
	}else if(sgn(r1+r2-d)==0){//tangent
		c1.args.push_back(normalize(theta));
	}else{
		Real phi=acos((r1+r2)/d);
		c1.args.push_back(normalize(theta+phi));
		c1.args.push_back(normalize(theta-phi));
	}
}

Point poles[8];
int N;
Circle circles[8];

vector<Point> pts;

Real dis[330][330];

Real X,Y;
Point start,goal;

int main(){
	for(int i=0;i<330;i++) for(int j=0;j<330;j++) dis[i][j]=inf;
	scanf("%d",&N);
	scanf("%lf%lf",&X,&Y);
	start=Point(0,0);
	goal=Point(X,Y);
	for(int i=0;i<N;i++){
		Real x,y;
		scanf("%lf%lf",&x,&y);
		poles[i]=Point(x,y);
		circles[i]=Circle(poles[i],100);
	}
	for(int i=0;i<N;i++) for(int j=0;j<N;j++){
		if(i==j) continue;
		iCC(circles[i],circles[j]);
		if(circles[i].args.size()>0&&isnan(circles[i].args.back())) printf("%d %d\n",i,j);
	}
	for(int i=0;i<N;i++){
		tCP(circles[i],start);
		if(circles[i].args.size()>0&&isnan(circles[i].args.back())) printf("%d st\n",i);
		tCP(circles[i],goal);
		if(circles[i].args.size()>0&&isnan(circles[i].args.back())) printf("%d go\n",i);
	}
	for(int i=0;i<N;i++) for(int j=0;j<N;j++){
		if(i==j) continue;
		itCC(circles[i],circles[j]);
		if(circles[i].args.size()>0&&isnan(circles[i].args.back())) printf("%d %d b\n",i,j);
		otCC(circles[i],circles[j]);
		if(circles[i].args.size()>0&&isnan(circles[i].args.back())) printf("%d %d c\n",i,j);
	}
	for(int i=0;i<N;i++){
		vector<Real> &args=circles[i].args;
		sort(args.begin(),args.end());
		int id=pts.size();
		vector<Real> tmp;
		for(int j=0;j<args.size();j++){
			Real cur=args[j];
			Real nxt=args[(j+1)%args.size()];
			if(j+1==args.size()) nxt+=PI*2;
			Real arg=(cur+nxt)/2.0;
			Point mid=circles[i].center+Vector(cos(arg),sin(arg))*circles[i].r;
			bool ok=true;
			for(int k=0;k<N;k++){
				if(cCP(circles[k],mid)) ok=false;
			}
			if(ok){
				tmp.push_back((nxt-cur)*circles[i].r);
			}
			else tmp.push_back(inf);
		}
		for(int j=0;j<args.size();j++){
			pts.push_back(circles[i].center+Vector(cos(args[j]),sin(args[j]))*circles[i].r);
		}
		for(int j=0;j<args.size();j++){
			dis[id+j][id+(j+1)%args.size()]=tmp[j];
			dis[id+(j+1)%args.size()][id+j]=tmp[j];
		}
		for(int j=0;j<args.size();j++){
			for(int k=0;k<id;k++){
				Segment seg=Segment(pts[id+j],pts[k]);
				bool ok=true;
				for(int l=0;l<N;l++){
					if(iCS(circles[l],seg)) ok=false;
				}
				if(ok){
					dis[id+j][k]=abs(pts[id+j]-pts[k]);
					dis[k][id+j]=abs(pts[id+j]-pts[k]);
				}else{
					dis[id+j][k]=inf;
					dis[k][id+j]=inf;
				}
			}
		}
	}
	Point p_[]={start,goal};
	for(int i=0;i<2;i++){
		int id=pts.size();
		pts.push_back(p_[i]);
		for(int j=0;j<id;j++){
			Point p=p_[i];
			Point q=pts[j];
			Segment seg=Segment(p,q);
			bool ok=true;
			for(int k=0;k<N;k++){
				if(iCS(circles[k],seg)){
					ok=false;
				}
			}
			if(ok){
				dis[j][id]=abs(pts[j]-pts[id]);
				dis[id][j]=abs(pts[j]-pts[id]);
			}else{
				dis[j][id]=inf;
				dis[id][j]=inf;
			}
		}
	}
	int V=pts.size();
	for(int i=0;i<V;i++) dis[i][i]=0;
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++) for(int j=0;j<V;j++){
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
	Real ans=dis[V-2][V-1];
	if(ans>5e8){
		ans=0;
	}
	printf("%.9f\n",ans);
	return 0;
}