HDU 4720 Naive and Silly Muggles

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 x 

i and y 

i (|x 

i, y 

i| <= 10), indicating the three wizards' positions. Then a single line with two numbers q 

x and q 

y (|q 

x, q 

y| <= 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

圓心要麼是三角形外心要麼是最大邊點的中點。

#include<stdio.h>
#include<math.h>
int T,n;
double x[3],y[3],a,b,c,X,Y,p,q,X0,Y0,R;

int main()
{
  scanf("%d",&T);
  for (int j=1;j<=T;j++)
  {
    for (int i=0;i<3;i++) scanf("%lf%lf",&x[i],&y[i]);
    a=(x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]);
    b=(x[0]-x[2])*(x[0]-x[2])+(y[0]-y[2])*(y[0]-y[2]);
    c=(x[1]-x[2])*(x[1]-x[2])+(y[1]-y[2])*(y[1]-y[2]);
    p=(a+b+c)/2;
    q=1/(1/(p-a)+1/(p-b)+1/(p-c));
    X=(1-q/(p-a))*x[2]+(1-q/(p-b))*x[1]+(1-q/(p-c))*x[0];
    Y=(1-q/(p-a))*y[2]+(1-q/(p-b))*y[1]+(1-q/(p-c))*y[0];
    X/=2;
    Y/=2;
    R=(X-x[0])*(X-x[0])+(Y-y[0])*(Y-y[0]);
    if (a>=b+c) {X=(x[0]+x[1])/2; Y=(y[0]+y[1])/2; R=a/4;}
    if (b>=a+c) {X=(x[0]+x[2])/2; Y=(y[0]+y[2])/2; R=b/4;}
    if (c>=a+b) {X=(x[2]+x[1])/2; Y=(y[2]+y[1])/2; R=c/4;}
    scanf("%lf%lf",&X0,&Y0);
    printf("Case #%d: ",j);
    if ((X-X0)*(X-X0)+(Y-Y0)*(Y-Y0)>R) printf("Safe\n"); 
    else printf("Danger\n");
  }
  return 0;
}      

#include<map>   
#include<set>  
#include<ctime>    
#include<cmath>   
#include<stack>
#include<queue>     
#include<string>    
#include<vector>    
#include<cstdio>        
#include<cstring>      
#include<iostream>    
#include<algorithm>        
#include<functional>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))        
#define rep(i,j,k) for(int i=j;i<=k;i++)        
#define per(i,j,k) for(int i=j;i>=k;i--)        
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])        
#define inone(x) scanf("%d",&x)        
#define intwo(x,y) scanf("%d%d",&x,&y)        
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)      
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)     
#define lson x<<1,l,mid    
#define rson x<<1|1,mid+1,r    
#define mp(i,j) make_pair(i,j)    
#define ff first    
#define ss second    
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const double eps = 1e-8;
int T, n, cas = 1;
double a[3], b[3], c[3], x, y, r, u, v;

double get(int i, int j)
{
  return (a[i] - a[j])*(a[i] - a[j]) + (b[i] - b[j])*(b[i] - b[j]);
}

double calc(double x, double y, double a, double b, double c, double d)
{
  double A = sqrt((x - a)*(x - a) + (y - b)*(y - b));
  double B = sqrt((x - c)*(x - c) + (y - d)*(y - d));
  double C = sqrt((a - c)*(a - c) + (b - d)*(b - d));
  return acos((A*A + B*B - C*C) / (2 * A*B));
}

int main()
{
  for (inone(T); T--; cas++)
  {
    rep(i, 0, 2) scanf("%lf%lf", &a[i], &b[i]);
    rep(i, 0, 2) c[i] = get(i, (i + 1) % 3);
    scanf("%lf%lf", &u, &v);
    printf("Case #%d: ", cas);
    sort(c, c + 3);  r = c[2] / 4;
    if (c[0] + c[1] <= c[2])
    {
      rep(i, 0, 2)
      {
        if (fabs(c[2] - get(i, (i + 1) % 3)) < eps)
        {
          x = (a[i] + a[(i + 1) % 3]) / 2;
          y = (b[i] + b[(i + 1) % 3]) / 2;
          break;
        }
      }
      if ((u - x)*(u - x) + (v - y)*(v - y) <= r) puts("Danger");
      else puts("Safe");
    }
    else
    {
      int flag = 0;
      double sum = 0;
      rep(i, 0, 2)
      {
        double ca = calc(u, v, a[(i + 1) % 3], b[(i + 1) % 3], a[(i + 2) % 3], b[(i + 2) % 3]);
        double cb = calc(a[i], b[i], a[(i + 1) % 3], b[(i + 1) % 3], a[(i + 2) % 3], b[(i + 2) % 3]);
        if (ca + cb >= acos(-1.0)) flag = 1;
        sum += ca;
      }
      if (fabs(sum - 2 * acos(-1.0)) < eps) puts("Danger");
      else puts(flag ? "Danger" : "Safe");
    }
  }
  return 0;
}