4667 Building Fence 解题报告

题意：给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<