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

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:

 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) 

代码形式:

 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

 此题代码为:

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

35230
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

12410
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44830
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51620
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18430
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13750
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30940
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

16220
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22540

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励