首页 > 代码库 > HDOJ 4720 Naive and Silly Muggles 三角形外接圆

HDOJ 4720 Naive and Silly Muggles 三角形外接圆

2024-10-28 04:43:39   209人阅读


当是钝角三角形时,就是最长边为直径的圆最小.

否则,求三角形的外接圆

Naive and Silly Muggles

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 700    Accepted Submission(s): 451


Problem Description
Three wizards are doing a experiment. To avoid from bothering, a special magic is set around them. The magic forms a circle, which covers those three wizards, in other words, all of them are inside or on the border of the circle. And due to save the magic power, circle‘s area should as smaller as it could be.
Naive and silly "muggles"(who have no talents in magic) should absolutely not get into the circle, nor even on its border, or they will be in danger.
Given the position of a muggle, is he safe, or in serious danger?
 

Input
The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case there are four lines. Three lines come each with two integers xi and yi (|xi, yi| <= 10), indicating the three wizards‘ positions. Then a single line with two numbers qx and qy (|qx, qy| <= 10), indicating the muggle‘s position.
 

Output
For test case X, output "Case #X: " first, then output "Danger" or "Safe".
 

Sample Input
3
0 0
2 0
1 2
1 -0.5

0 0
2 0
1 2
1 -0.6

0 0
3 0
1 1
1 -1.5
 

Sample Output
Case #1: Danger
Case #2: Safe
Case #3: Safe
 

Source
2013 ACM/ICPC Asia Regional Online —— Warmup2
 

Recommend
zhuyuanchen520   |   We have carefully selected several similar problems for you:  5157 5156 5155 5154 5153 
 

Statistic | Submit | Discuss | Note


/* ***********************************************
Author        :CKboss
Created Time  :2015年01月07日 星期三 23时26分30秒
File Name     :HDOJ4720.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

double eps = 1e-10;

int dcmp(double x) { if(fabs(x)<eps) return 0; return (x<0)?-1:1;}

struct Point
{
    double x,y;
    Point(double _x,double _y):x(_x),y(_y){}
    Point(){}
};

Point operator-(Point A,Point B) {return Point(A.x-B.x,A.y-B.y);}

struct Circle
{
    Point c;
    double r;
    Circle(Point _c,double _r):c(_c),r(_r){}
};

double Dot(Point A,Point B) { return A.x*B.x+A.y*B.y; }
double Length(Point A) { return sqrt(Dot(A,A)); }

Circle CircumscribedClircle(Point p1,Point p2,Point p3)
{
    double Bx=p2.x-p1.x,By=p2.y-p1.y;
    double Cx=p3.x-p1.x,Cy=p3.y-p1.y;
    double D=2*(Bx*Cy-By*Cx);
    double cx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
    double cy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;
    Point p = Point(cx,cy);
    return Circle(p,Length(p1-p));
}

Point p1,p2,p3,pp;

bool check(Circle c , Point p)
{
    double l1 = Length(c.c-p);
    double l2 = c.r;

    if(dcmp(l1-l2)<=0) return false;
    return true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T_T,cas=1;
    scanf("%d",&T_T);
    while(T_T--)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        p1=Point(x,y);
        scanf("%lf%lf",&x,&y);
        p2=Point(x,y);
        scanf("%lf%lf",&x,&y);
        p3=Point(x,y);
        scanf("%lf%lf",&x,&y);
        pp=Point(x,y);

        // two point on the magic circle

        printf("Case #%d: ",cas++);
        /// p1 ... p2
        double rrr = Length(p1-p2)/2;
        Point ppp = Point((p1.x+p2.x)/2,(p1.y+p2.y)/2);
        Circle ccc = Circle(ppp,rrr);
        if(check(ccc,p3)==false)
        {
            if(check(ccc,pp)==true) puts("Safe");
            else puts("Danger");
            continue;
        }
        /// p2...p3
        rrr = Length(p2-p3)/2;
        ppp = Point((p2.x+p3.x)/2.,(p2.y+p3.y)/2.);
        ccc = Circle(ppp,rrr);
        if(check(ccc,p1)==false)
        {
            if(check(ccc,pp)==true) puts("Safe");
            else puts("Danger");
            continue;
        }
        /// p1...p3
        rrr = Length(p1-p3)/2;
        ppp = Point((p1.x+p3.x)/2.,(p1.y+p3.y)/2.);
        ccc = Circle(ppp,rrr);
        if(check(ccc,p2)==false)
        {
            if(check(ccc,pp)==true) puts("Safe");
            else puts("Danger");
            continue;
        }


        /// three point on circle
        Circle cc = CircumscribedClircle(p1,p2,p3);
        double len = Length(cc.c-pp);
        if(dcmp(len-cc.r)<=0) puts("Danger");
        else puts("Safe");
    }
    
    return 0;
}


HDOJ 4720 Naive and Silly Muggles 三角形外接圆


联系
我们