HDUOJ 4720 Naive and Silly Muggles

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <vector>

using namespace std;

const double eps = 1e-7;
const double inf = 1e7;

bool db_eq(const double& a, const double& b){return fabs(a-b)<=eps;}
bool db_bt(const double& a, const double& b){return a>b+eps;}
bool db_st(const double& a, const double& b){return a+eps<b;}
bool db_be(const double& a, const double& b){return a>=b-eps;}
bool db_se(const double& a, const double& b){return a<=b+eps;}

struct pt{
    double x, y;
    pt(double _x = 0, double _y = 0): x(_x), y(_y){} 
    double len()const{return sqrt(x*x+y*y);}
};

pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
pt operator/(const pt& a, const double& r){return pt(a.x/r, a.y/r);}
double operator^(const pt& a, const pt& b){return a.x*b.y-a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}

struct line{
    // ax + by + c = 0;
    double a, b, c;
    line(){
        a = 0, b = 0, c = 0;
    }
    line(const pt& m, const pt& s){
        a = m.y, b = -m.x;
        c = -(a*s.x+b*s.y);
    }
    pt m()const{
        return pt(-b, a);
    }
};

pt operator*(const line& l1, const line& l2){
    double det = l1.m()^l2.m();
    if(db_eq(det, 0)) return pt(inf, inf);
    double detx = -l1.c*l2.b+l2.c*l1.b;
    double dety =  l1.c*l2.a-l2.c*l1.a;
    return pt(detx/det, dety/det);
}

struct cir{
    pt o;
    double r;
    cir(const pt& _o = pt(), const double& _r = 0): o(_o), r(_r){}
    cir(const pt& pt1, const pt& pt2){o = (pt1+pt2)/2; r = (pt1-o).len();}
    
    cir(const pt& pt1, const pt& pt2, const pt& pt3){
        line l1 = line(~(pt2-pt1), (pt1+pt2)/2);
        line l2 = line(~(pt3-pt1), (pt1+pt3)/2);
        o = l1*l2;
        if(db_eq(o.x, inf)){
            double l12 = (pt1-pt2).len(),
                   l23 = (pt2-pt3).len(),
                   l13 = (pt3-pt1).len();
            if(db_eq(l12+l23,l13)) cir(pt1,pt3);
            else if(db_eq(l13+l23,l12)) cir(pt1,pt2);
            else if(db_eq(l12+l13,l23)) cir(pt2,pt3);
            else assert(0);
        }else{
            r = (o-pt1).len();
        }
    }
    bool has(const pt& p){ return db_bt((p-o).len(),r) == false;}
};

int main(){
    int T; scanf("%d", &T);
    for(int lt = 1;lt <= T;lt++){
        pt p[4],tt;
        for(int lx = 0;lx<4;lx++)
            scanf("%lf %lf", &p[lx].x, &p[lx].y);
        cir cc(p[0],p[1],p[2]);
        cir c01(p[0], p[1]);
        cir c12(p[1], p[2]);
        cir c02(p[0], p[2]);
        if(c01.has(p[2]) and db_st(c01.r, cc.r)) cc = c01;
        if(c02.has(p[1]) and db_st(c02.r, cc.r)) cc = c02;
        if(c12.has(p[0]) and db_st(c12.r, cc.r)) cc = c12;
        
        printf("Case #%d: %s\n", lt, cc.has(p[3])==false ? "Safe":"Danger");
    }
    return 0;
}