前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDUOJ-------Naive and Silly Muggles

HDUOJ-------Naive and Silly Muggles

作者头像
Gxjun
发布2018-03-21 12:47:46
6100
发布2018-03-21 12:47:46
举报
文章被收录于专栏:ml

Naive and Silly Muggles

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

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

几何题:

考虑的事情有:

       (1)三点是否在一条直线上...求出前后坐标,得出圆心,和半径r;

       (2)区分锐角和钝角三角形....锐角三角形(最小的圆为其外接圆),钝角三角形以最长边为直径做圆为其最小圆面积...

 于是 有一点必须要注意,那就是求 外接圆的中心坐标(x,y)

代码wei:

代码语言:javascript
复制
 1 通俗算法 
 2 定义:设平面上的三点A(x1,y1),B(x2,y2),C(x3,y3),定义
 3       S(A,B,C) = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
 4  
 5 已知三角形的三个顶点为A(x1,y1),B(x2,y2),C(x3,y3),则该三角形的外心为:
 6               S((x1*x1+y1*y1, y1), (x2*x2+y2*y2, y2), (x3*x3+y3*y3, y3))
 7      x0 = -----------------------------------------------------------
 8                                   2*S(A,B,C)
 9            
10               S((x1,x1*x1+y1*y1), (x2, x2*x2+y2*y2), (x3, x3*x3+y3*y3))
11      y0 = -----------------------------------------------------------
12                                   2*S(A,B,C) 

代码形式:

代码语言:javascript
复制
 1 //求外接圆的圆心
 2 double S(double x1,double y1,double x2,double y2,double x3,double y3){
 3     return ((x1-x3)*(y2-y3)   -   (y1-y3)*(x2-x3) );
 4 }
 5 
 6 double getx(double x1,double y1,double x2,double y2,double x3,double y3){
 7     return (S(x1*x1+y1*y1,y1, x2*x2+y2*y2, y2,x3*x3+y3*y3,y3)/(2*S(x1,y1,x2,y2,x3,y3)) );
 8 }
 9 
10 double gety(double x1,double y1,double x2,double y2,double x3,double y3){
11     return (S(x1, x1*x1+y1*y1, x2, x2*x2+y2*y2, x3, x3*x3+y3*y3) / (2*S(x1,y1,x2,y2,x3,y3)));
12 }

Sample Output

Case #1: Danger

Case #2: Safe

Case #3: Safe

 此题代码为:

代码语言:javascript
复制
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6  bool isline(double *a,double *b,double *c)
 7  {
 8     if(fabs((b[1]-a[1])*(c[0]-a[0])-(c[1]-a[1])*(b[0]-a[0]))<1e-8)
 9         return 1;
10     else 
11         return 0;
12  }
13 //求外接圆的圆心
14 double S(double x1,double y1,double x2,double y2,double x3,double y3){
15     return ((x1-x3)*(y2-y3)   -   (y1-y3)*(x2-x3) );
16 }
17 
18 double getx(double x1,double y1,double x2,double y2,double x3,double y3){
19     return (S(x1*x1+y1*y1,y1, x2*x2+y2*y2, y2,x3*x3+y3*y3,y3)/(2*S(x1,y1,x2,y2,x3,y3)) );
20 }
21 
22 double gety(double x1,double y1,double x2,double y2,double x3,double y3){
23     return (S(x1, x1*x1+y1*y1, x2, x2*x2+y2*y2, x3, x3*x3+y3*y3) / (2*S(x1,y1,x2,y2,x3,y3)));
24 }
25 //求两条边的夹角
26 bool iftrue(double *a,double *b,double *c )
27 {
28     return (a[0]-b[0])*(c[0]-b[0])+(a[1]-b[1])*(c[1]-b[1])>0?0:1;  //不是锐角时yes
29 }
30 //求两点间的距离
31 double distan(double *a,double *b)
32 {
33     return sqrt((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]))/2.0;
34 }
35 
36 int main()
37 {
38     int t,count,i;
39     double po[4][2],r,save[2][2],x,y;
40     scanf("%d",&t);
41     for(count=1;count<=t;count++)
42     {
43       for(i=0;i<4;i++)
44       {
45           scanf("%lf%lf",&po[i][0],&po[i][1]);
46           if(i==0||save[1][0]*save[1][0]+save[1][1]*save[1][1]<po[i][0]*po[i][0]+po[i][1]*po[i][1])
47               save[1][1]=po[i][1],save[1][0]=po[i][0];
48           if(i==0||save[0][0]*save[0][0]+save[0][1]*save[0][1]>po[i][0]*po[i][0]+po[i][1]*po[i][1])
49               save[0][1]=po[i][1],save[0][0]=po[i][0];
50       }
51       if(isline(po[0],po[1],po[2]))
52       {
53           r=sqrt((save[1][0]-save[0][0])*(save[1][0]-save[0][0])+(save[1][1]-save[0][1])*(save[1][1]-save[0][1]))/2.0;
54           x=(save[0][0]+save[1][0])/2.0;
55           y=(save[0][1]+save[1][1])/2.0;
56       }
57       else 
58       {
59           bool judge[3];
60                judge[0]=iftrue(po[0],po[1],po[2]);
61                judge[1]=iftrue(po[1],po[0],po[2]);
62                judge[2]=iftrue(po[1],po[2],po[0]);
63           if(judge[0]||judge[1]||judge[2])
64           {
65              if(judge[0])
66              {
67               x=(po[0][0]+po[2][0])/2.0;
68               y=(po[0][1]+po[2][1])/2.0;
69               r=distan(po[0],po[2]);
70              }
71              else if(judge[1])
72              {
73               x=(po[1][0]+po[2][0])/2.0;
74               y=(po[1][1]+po[2][1])/2.0;
75               r=distan(po[1],po[2]);
76              }
77              else if(judge[2])
78              {
79               x=(po[1][0]+po[0][0])/2.0;
80               y=(po[1][1]+po[0][1])/2.0;
81               r=distan(po[0],po[1]);
82              }
83           }
84           else
85           {
86             //当为锐角时,求其外接圆,否者不求
87             x=getx(po[0][0],po[0][1],po[1][0],po[1][1],po[2][0],po[2][1]);
88             y=gety(po[0][0],po[0][1],po[1][0],po[1][1],po[2][0],po[2][1]);
89             r=sqrt((po[2][0]-x)*(po[2][0]-x)+(po[2][1]-y)*(po[2][1]-y));
90           }
91       }
92       double temp=sqrt((po[3][0]-x)*(po[3][0]-x)+(po[3][1]-y)*(po[3][1]-y));
93        if(r>temp-1e-8)
94               printf("Case #%d: Danger\n",count);
95           else
96               printf("Case #%d: Safe\n",count);
97     }
98     return 0;
99 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-09-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Naive and Silly Muggles
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档