與原PO作法相同
公切線與距離等可善用cross及dot運算讓code簡潔不少
//by david942j
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
const int N=12;
const double EPS=1e-5;
struct node{
int p;
double c;
node *next;
}h[N*N*N];
struct unit{
double x,y;
int idx;
unit(double X,double Y){x=X;y=Y;}
unit(){}
unit operator-(const unit &A)const
{
unit tmp(x-A.x,y-A.y);
return tmp;
}
unit operator+(const unit &A)const
{
unit tmp(x+A.x,y+A.y);
return tmp;
}
unit operator*(const double &A)const
{
unit tmp(x*A,y*A);
return tmp;
}
double operator*(const unit &A)const
{return x*A.y-y*A.x;}
double dot(const unit &A)const
{return x*A.x+y*A.y;}
inline double len(){return sqrt(x*x+y*y);}
inline void normalize(){double l=len();x/=l;y/=l;}
bool operator<(const unit &B)const
{
unit A(x,y);
if(fabs(A.y)<EPS&&fabs(B.y)<EPS)return A.x>B.x;
if(A.y>0&&B.y<0)return true;
if(B.y>0&&A.y<0)return false;
return A*B>0;
}
//inline void out(){printf("- %.2lf %.2lf\n",x,y);}
}C[N];
int nodetop;
void add(int x,int y,double c)
{
//printf("add %d %d %lf\n",x,y,c);
node *tmp=new node;
tmp->p=y;tmp->c=c;
tmp->next=h[x].next;
h[x].next=tmp;
}
std::vector<unit>V[N];
void PonC(std::vector<unit>&V,unit &C,double &r)
{
int n=V.size();
for(int i=0;i<n;i++){
int idx=V[i].idx;
V[i]=V[i]-C;
V[i].idx=idx;
}
std::sort(V.begin(),V.end());
V.push_back(V[0]);
for(int i=0;i<n;i++)
{
double len=r*acos(V[i].dot(V[i+1])/r/r);
add(V[i].idx,V[i+1].idx,len);
add(V[i+1].idx,V[i].idx,len);
}
}
double R[N];
int n;
void PtoC(unit A,unit C,double r,unit &p,unit &q)
{
unit u=C-A;
double l=u.len(),d=sqrt(l*l-r*r);
u.normalize();
unit v(u.y,-u.x);
u=u*(d*d/l)+A;
v=v*(d*r/l);
p=u+v;
q=u-v;
}
void newnode(unit A,int pos)
{
//printf("%d: %lf %lf on %d\n",nodetop,A.x,A.y,pos);
h[A.idx=nodetop++].next=NULL;
V[pos].push_back(A);
}
inline void swap(int &A,int &B){int tmp=A;A=B;B=tmp;}
bool ok(unit A,unit B)
{
unit u=B-A,v;
double L=u.len();
u.normalize();
for(int i=1;i<=n;i++)
{
v=C[i]-A;
double t=u.dot(v)/L;
if(t<EPS||t>1.0-EPS)continue;
if(R[i]>fabs(u*v)/u.len()+EPS)return false;
}
return true;
}
void calc(int p1,int p2)
{
if(R[p1]>R[p2])swap(p1,p2);
double &r1=R[p1],&r2=R[p2];
unit &c1=C[p1],&c2=C[p2],A[2]={(c2-c1)*(r1/(r1+r2))+c1,(c1-c2)*(r2/(r2-r1))+c2};
unit a1,b1,a2,b2;
for(int i=0;i<2;i++)
{
if(i&&fabs(r1-r2)<EPS)
{
unit u=c2-c1;
u.normalize();
unit v(u.y,-u.x);
a1=v*r1+c1;
a2=v*r2+c2;
b1=v*-r1+c1;
b2=v*-r2+c2;
}
else{
PtoC(A[i],c1,r1,a1,b1);
PtoC(A[i],c2,r2,a2,b2);
}
if(ok(a1,a2))
{
newnode(a1,p1);
newnode(a2,p2);
add(nodetop-1,nodetop-2,(a1-a2).len());
add(nodetop-2,nodetop-1,(a1-a2).len());
}
if(ok(b1,b2))
{
newnode(b1,p1);
newnode(b2,p2);
add(nodetop-1,nodetop-2,(b1-b2).len());
add(nodetop-2,nodetop-1,(b1-b2).len());
}
}
}
double dis[N*N*N];
double SPFA(int s,int t,int n)
{
bool flag[N*N*N]={};
for(int i=0;i<n;i++)dis[i]=1e30;
std::queue<int>Q;
Q.push(s);
dis[s]=0.0;
while(!Q.empty())
{
int x=Q.front();Q.pop();
flag[x]=false;
for(node *tmp=h[x].next;tmp;tmp=tmp->next)
if(dis[tmp->p]>dis[x]+tmp->c)
{
dis[tmp->p]=dis[x]+tmp->c;
if(!flag[tmp->p])flag[tmp->p]=true,Q.push(tmp->p);
}
}
return dis[t];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
nodetop=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf",&C[i].x,&C[i].y,&R[i]);
for(int i=0;i<=n;i++)V[i].clear();
unit s(0,0),t(1000,1000);
if(ok(s,t))
{
printf("%.2lf\n",(t-s).len());
continue;
}
newnode(s,0);
newnode(t,0);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
calc(i,j);
for(int i=1;i<=n;i++)
{
unit a,b;
PtoC(s,C[i],R[i],a,b);
if(ok(s,a))
{
newnode(a,i);
add(0,nodetop-1,(s-a).len());
add(nodetop-1,0,(s-a).len());
}
if(ok(s,b))
{
newnode(b,i);
add(0,nodetop-1,(s-b).len());
add(nodetop-1,0,(s-b).len());
}
unit c,d;
PtoC(t,C[i],R[i],c,d);
if(ok(t,c))
{
newnode(c,i);
add(1,nodetop-1,(t-c).len());
add(nodetop-1,1,(t-c).len());
}
if(ok(t,d))
{
newnode(d,i);
add(1,nodetop-1,(t-d).len());
add(nodetop-1,1,(t-d).len());
}
}
for(int i=1;i<=n;i++)
PonC(V[i],C[i],R[i]);
printf("%.2lf\n",SPFA(0,1,nodetop));
}
}
NPSC補完計劃 » NPSC高中組 » NPSC2010高中組決賽
NPSC 2010 高中組 決賽 G.
