hdu 4720

最小覆盖圆的模板；

#include<stdio.h>
#include<string.h>
#include<math.h>
struct Point
{
    double x;
    double y;
} pt[1005];
struct Traingle
{
    struct Point p[3];
};
struct Circle
{
    struct Point center;
    double r;
} ans;
//计算两点距离
double Dis(struct Point p, struct Point q)
{
    double dx=p.x-q.x;
    double dy=p.y-q.y;
    return sqrt(dx*dx+dy*dy);
}
//计算三角形面积
double Area(struct Traingle ct)
{
    return
        fabs((ct.p[1].x-ct.p[0].x)*(ct.p[2].y-ct.p[0].y)-(ct.p[2].x-ct.p[0].x)*(ct.p[1].y-ct.p[0].y))/2.0;
}
//求三角形的外接圆，返回圆心和半径(存在结构体"圆"中)
struct Circle CircumCircle(struct Traingle t)
{
    struct Circle tmp;
    double a, b, c, c1, c2;
    double xA, yA, xB, yB, xC, yC;
    a = Dis(t.p[0], t.p[1]);
    b = Dis(t.p[1], t.p[2]);
    c = Dis(t.p[2], t.p[0]);
//根据S = a * b * c / R / 4;求半径R
    tmp.r = (a*b*c)/(Area(t)*4.0);
    xA = t.p[0].x;
    yA = t.p[0].y;
    xB = t.p[1].x;
    yB = t.p[1].y;
    xC = t.p[2].x;
    yC = t.p[2].y;
    c1 = (xA*xA+yA*yA - xB*xB-yB*yB) / 2;
    c2 = (xA*xA+yA*yA - xC*xC-yC*yC) / 2;
    tmp.center.x = (c1*(yA - yC)-c2*(yA - yB)) / ((xA - xB)*(yA - yC)-(xA - xC)*(yA - yB));
    tmp.center.y = (c1*(xA - xC)-c2*(xA - xB)) / ((yA - yB)*(xA - xC)-(yA - yC)*(xA - xB));
    return tmp;
}
//确定最小包围圆
struct Circle MinCircle(int num, struct Traingle ct)
{
    struct Circle ret;
    if (num==0) ret.r = 0.0;
    else if (num==1)
    {
        ret.center = ct.p[0];
        ret.r = 0.0;
    }
    else if (num==2)
    {
        ret.center.x = (ct.p[0].x+ct.p[1].x)/2.0;
        ret.center.y = (ct.p[0].y+ct.p[1].y)/2.0;
        ret.r = Dis(ct.p[0], ct.p[1])/2.0;
    }
    else if(num==3) ret = CircumCircle(ct);
    return ret;
}
//递归实现增量算法
void Dfs(int x, int num, struct Traingle ct)
{
    int i, j;
    struct Point tmp;
    ans = MinCircle(num, ct);
    if (num==3) return;
    for (i=1; i<=x; i++)
        if (Dis(pt[i], ans.center)>ans.r)
        {
            ct.p[num]=pt[i];
            Dfs(i-1, num+1, ct);
            tmp=pt[i];
            for (j=i; j>=2; j--)
                pt[j]=pt[j-1];
            pt[1]=tmp;
        }
}
void Solve(int n)
{
    struct Traingle ct;
    Dfs(n, 0, ct);
}
int main (void)
{
    int n, i,t;
    int ca=1;
    scanf("%d",&t);
    while (t--)
    {
        for (i=1; i<=3; i++)
            scanf("%lf %lf", &pt[i].x, &pt[i].y);
        Solve(3);
        double xx,yy;
        scanf("%lf%lf",&xx,&yy);
        printf("Case #%d: ",ca++);
        if((xx-ans.center.x)*(xx-ans.center.x)+(yy-ans.center.y)*(yy-ans.center.y)<=(ans.r)*(ans.r))
            puts("Danger");
        else puts("Safe");
    }
    return 0;
}