jj同学对算法相当痴迷，可是他最近迷恋上了6-420班的ll同学，这让他无法静下心来研究算法。他通过ljy小朋友打听到z同学比较看好有才华的男生，特别是算法比较强的；于是他设想：如果它能给z同学讲解一个牛的算法，她对他的好感肯定会倍增。于是他就计划在2011年11月11日那天给ll同学讲解一个他精心的设计的算法题，经过深入的思考设计了下面的问题：在平面坐标系内竖直放置了多个粗细不同的圆柱，那么至少需要多长的绳子才能把这些圆柱全都围起来呢？虽然jj同学已经成功解决了这个问题，但还是想通过大家得到一些更好的解决方案来为他赢得更多的好感。
- 输入
-
包含多组测试数据,相邻的两组测试数据间有一个空行.每组测试数据，第一行为一个正整数num(num<=100)表示有多少个圆柱，接下来num行，每行有3个实数xi,yi,ri;其中xi,yi表示圆柱中轴在坐标系内的坐标，ri表示圆柱的半径。当然不会出现圆柱相交，包含的现象。
- 输出
-
对于每组测试数据，输出一个实数，绳子的最短长度，并精确到小数点后4位。
- 样例输入
-
2 0 0 1 3 0 1
- 样例输出
-
12.2832
纯数学题
#include<stdio.h>
#include<string.h>
#include "math.h"
#include<stdlib.h>
const int MAXN=100;
const double PI2=acos(-1.0)*2.0;
const double EPS=1e-5;
struct REC{
double x,y,r;
}list[MAXN];
int ptr[2*MAXN];
char flag[MAXN][MAXN];
inline double arctan(const double& dy,const double& dx)
{
double t=atan2(dy,dx);
if(t<0)
t+=PI2;
return t;
}
void normalize(double &ang)
{
if(ang<0)
ang+=PI2;
else if(ang>PI2)
ang-=PI2;
}
double distance(REC& a,REC& b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double calc(REC& a,REC& b,REC& c)
{
double ret=0.0;
double ang_in,ang_out;
double d,ang,deltar,l,theta;
ang=arctan(a.y-b.y,a.x-b.x);
d=distance(a,b);
deltar=a.r-b.r;
theta=asin(deltar/d);
ang_in=ang+theta+PI2/4.0;
ang=arctan(c.y-b.y,c.x-b.x);
d=distance(b,c);
deltar=c.r-b.r;
theta=asin(deltar/d);
ang_out=ang-theta-PI2/4.0;
if(ang_out<ang_in)
ang_out+=PI2;
ret=b.r*(ang_out-ang_in);
l=sqrt(d*d-deltar*deltar);
return ret+l;
}
int main()
{
int N,i;
char c;
while(true)
{
scanf("%d",&N);
double ymin=1e50,xmin=1e50;
int ori=-1;
for(i=0;i<N;i++)
{
scanf("%lf %lf %lf",&list[i].x,&list[i].y,&list[i].r);
if(list[i].y-list[i].r<ymin)
{
ymin=list[i].y-list[i].r;
xmin=list[i].x;
ori=i;
}
else if(list[i].y-list[i].r<ymin+EPS&&list[i].x<xmin)
{
xmin=list[i].x;
ori=i;
}
}
int p;
double last=-1.0;
memset(flag,0,sizeof(flag));
ptr[0]=ori;
//printf("%.3lf %.3lf %.3lf\n",list[ori].x,list[ori].y,list[ori].r);
for(p=1;;p++)
{
int sel=-1;
double amin=1.0e10,len=-1.0;
double d,deltar,ang,theta,l;
for(i=0;i<N;i++)
{
if(ptr[p-1]==i)
continue;
ang=arctan(list[i].y-list[ptr[p-1]].y,list[i].x-list[ptr[p-1]].x);
d=distance(list[i],list[ptr[p-1]]);
deltar=list[i].r-list[ptr[p-1]].r;
theta=asin(deltar/d);
ang-=theta;
normalize(ang);
l=sqrt(d*d-deltar*deltar);
if(ang<last)
ang+=PI2;
if(ang<amin-EPS)
{
amin=ang;
len=l;
sel=i;
}
else if(ang<amin+EPS)
{
if(l>len)
{
len=l;
sel=i;
}
}
}
last=amin;
//printf("%.3lf %.3lf %.3lf\n",list[sel].x,list[sel].y,list[sel].r);
ptr[p]=sel;
if(flag[ptr[p-1]][ptr[p]])
break;
flag[ptr[p-1]][ptr[p]]=1;
}
N=p-1;
double acc;
acc=calc(list[ptr[N-1]],list[ptr[0]],list[ptr[1]]);
for(i=1;i<N;i++)
acc+=calc(list[ptr[i-1]],list[ptr[i]],list[ptr[i+1]]);
printf("%.4lf\n",acc);
c=getchar();
if(c!='\n')
break;
}
return 0;
}