c_wa.cpp

ACM World Final 2008题目程序代码

// not accepted yet (need your help! )
#include <cstdio>
#include <cstring>
#include <complex>
using namespace std;

const double eps=1e-4;
typedef complex<double> comp;

double dot(const comp& c1,const comp& c2)
{
	return c1.real()*c2.real()+c1.imag()*c2.imag();
}

double cross(const comp& c1,const comp& c2)
{
	return c1.real()*c2.imag()-c1.imag()*c2.real();
}

struct circle
{
	comp o;
	double r;
	void read()
	{
		double x,y;
		scanf("%lf %lf %lf C",&x,&y,&r);
		o=comp(x,y);
		int sign=0;
		scanf("C%n",&sign);
		if(sign)r=-r;
	}
};

struct vec
{
	comp s,t;
	double len;
	vec(){}
	vec(const circle& cs,const circle& ct)
	{
		comp ost=ct.o-cs.o;
		double cosd=(cs.r-ct.r)/abs(ost);
		double sind=sqrt(1.0-cosd*cosd);
		comp d(cosd,sind);
		d*=ost/abs(ost);
		s=cs.o+d*cs.r;
		t=ct.o+d*ct.r;
		len=abs(t-s);
	}
};

double arclen(const comp& s,const comp& t,double r)
{
	return r+=r,r*asin(abs(s-t)/r);
}

bool in(const circle& c,const vec& v)
{
	comp so=c.o-v.s,st=v.t-v.s;
	double h=cross(so,st)/v.len;
	double h2=h*h,r2=c.r*c.r+eps;
	if(r2<h2)return false;
	double m=dot(so,st)/v.len,d=sqrt(r2-h2);
	return m-d<=v.len && 0.0<=m+d;
}

bool cr(const vec& v,const vec& vb)
{
	return cross(v.s-vb.s,vb.t-vb.s)*cross(v.t-vb.s,vb.t-vb.s)<=0;
}

bool in(const vec& v1,const vec& v2)
{
	return cr(v1,v2) && cr(v2,v1);
}

const double INF=HUGE_VAL;

circle sh[22];
vec vel[440];
int n,s,t,nol[22],ve[22],velno[22][22],velsize,r;
double de,mindis;
bool v[22],can[440][440];

double dis()
{
	double ans=0.0;
	for(int i=1;i<r;++i)
		ans+=arclen(vel[ve[i]].t,vel[ve[i+1]].s,sh[nol[i]].r);
	for(int i=1;i<=r;++i)
		ans+=vel[ve[i]].len;
	return ans;
}

bool test(int no)
{
	ve[r]=velno[nol[r-1]][nol[r]=no];
	if(!ve[r])return false;
	for(int i=1;i<r;++i)if(!can[ve[i]][ve[r]])return false;
	return true;
}

void search()
{
	if(nol[r]==t)
	{
		double c=dis();
		if(c<mindis)mindis=c;
		return;
	}
	v[nol[r++]]=true;
	for(int i=0;i<n;++i)if(!v[i] && test(i))search();
	v[nol[--r]]=false;
}

bool vev(int s,int t,const vec& x)
{
	if(x.len>=de)return false;
	for(int i=0;i<n;++i)if(i!=s && i!=t)
		if(in(sh[i],x))return false;
	return true;
}

void prework()
{
	velsize=0;
	memset(velno,0,sizeof(velno));
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)if(j!=i)
		{
			vec x(sh[i],sh[j]);
			if(vev(i,j,x))vel[velno[i][j]=++velsize]=x;
		}
	memset(can,0,sizeof(can));
	for(int i=1;i<=velsize;++i)
		for(int j=1;j<=velsize;++j)if(j!=i)
			can[i][j]=!in(vel[i],vel[j]);
	memset(v,0,sizeof(v));
	mindis=INF;
	nol[r=0]=s;
}

int main()
{
	for(int te=1;scanf("%d",&n),n;++te)
	{
		for(int i=0;i<n;++i)sh[i].read();
		scanf("%d %d %lf",&s,&t,&de);
		prework(),search();
		printf("Case %d: ",te);
		if(mindis!=INF)
		{
			char s[100],*t;
			t=s+sprintf(s,"length = %.2lf",mindis)-1;
			while(*t=='0')--t;
			if(*t=='.')--t;
			t[1]=0;
			puts(s);
		}
		else printf("Cannot reach destination shaft\n");
	}
	return 0;
}