题意:给n个圆和m个三角形,且保证互不相交,用一个篱笆把他们围起来,求最短的周长是多少。
解法1:在每个圆上均匀的取2000个点,求凸包周长就可以水过。
解法2:求出所有圆之间的外公切线的切点,以及过三角形每个顶点的的直线和圆的切点,和三角形的三个顶点。这些点做凸包确定篱笆边上的图形。凸包的边和圆弧之和即为所求。求圆弧长度的时候要判断是优弧还是劣弧。用叉积判断两个向量的方向关系即可。
//Time:218MS
//Memory:860K
include
#include
#include
#include
#include
using namespace std;
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int MAXN = 55;
int dcmp(double x)
{
if(fabs(x) 1 && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-2; i >= 0; i--)
{
while(m > k && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;
ch[m++] = p[i];
}
if(n > 1) m--;
return m;
}
Vector rotate(Vector a,double rad)
{
Vector c;
c.x = a.x*cos(rad)-a.y*sin(rad);
c.y = a.x*sin(rad)+a.y*cos(rad);
return c;
}
void get_ocmt(Circle c1,Circle c2,Point &s1, Point &e1,Point &s2,Point &e2)
{
double l = dist(c1.o,c2.o);
double d = fabs(c1.r-c2.r);
double theta = acos(d/l);
//if(dcmp(c1.r-c2.r)>0) swap(c1,c2);
Vector vec = c1.o-c2.o;
vec = vec.trunc(c1.r);
s1 = c1.o+rotate(vec,theta);
s2 = c1.o+vec.rotate(-theta);
vec = vec.trunc(c2.r);
e1 = c2.o+vec.rotate(theta);
e2 = c2.o+vec.rotate(-theta);
}
void get_pc(Circle c, Point p,Point &s1,Point &s2)
{
Vector u = p-c.o;
double dist = length(u);
Point v = c.o+u/dist*c.r;
double ang = PI/2-asin(c.r/dist);
s1 = rotate(v-c.o,-ang)+c.o;
s2 = rotate(v-c.o,ang)+c.o;
}
Point p[55*55*55],ch[55*55*55];
int main()
{
//freopen("/home/qitaishui/code/in.txt","r",stdin);
int n,m,pn,chn;
Circle c[MAXN];
Tri tri[MAXN];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i = 0; i < n;i++)
{
c[i].o.input();
scanf("%lf",&c[i].r);
}
if(n==1&&m==0)
{
printf("%.6f\n",c[0].len(2*PI));
continue;
}
for(int i = 0; i < m; i++)
for(int j = 0; j < 3; j++)
tri[i].p[j].input();
pn = 0;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{
if(dcmp(c[i].r-c[j].r)>0)
get_ocmt(c[j],c[i],p[pn+1],p[pn],p[pn+3],p[pn+2]);
else
get_ocmt(c[i],c[j],p[pn],p[pn+1],p[pn+2],p[pn+3]);
p[pn].tp = 0,p[pn].id = i;
p[pn+1].tp = 0,p[pn+1].id = j;
p[pn+2].tp = 0,p[pn+2].id = i;
p[pn+3].tp = 0,p[pn+3].id = j;
pn+=4;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
for(int k = 0; k <3; k++)
{
get_pc(c[i],tri[j].p[k],p[pn],p[pn+1]);
p[pn].tp = 0,p[pn].id = i;
p[pn+1].tp = 0,p[pn+1].id = i;
pn+=2;
}
for(int j = 0; j < m; j++)
for(int k = 0; k <3; k++)
{
p[pn] = tri[j].p[k];
p[pn].tp = 1, p[pn].id = j;
pn++;
}
chn = ConvexHull(p,pn,ch);
//cout<