cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus

time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Input

The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

Output

Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

Sample test(s)

Input

0.000000 0.000000
1.000000 1.000000
0.000000 1.000000

Output

1.00000000

这道题的题意是: 以一个场地遗迹,呈现多边形,但是不知道具体是几边形,只知道他的三个点,求能包含这三个点的最小多边形的面积:
 对于这样的题目: 思路为:
  先求出他的外接圆,得到外接圆的半径rr.
  (1外接圆的求法: 
{
    (1) 有给定的坐标我们不难求出三条边的边长,rea,reb,rec;
    (2) 又海伦公式得到三角形的面积: 周长cc=(rea+reb+rec)/2.0 面积等于: ss=sqrt(cc*(cc-rea)*(cc-reb)*(cc-rec));
    (3) rr=rea*reb*rec/(4*ss);  //证明就不详细说了
}
得到外接园的半径之后:
   我们再来求出每一条边对应的圆心角a,b,c;
   求出a,b,c圆心角的最大公约数st;
这样我们就可以知道他是边数: 2*pi/st;
所以得到最小单位的三角形的面积为Area=rr*rr*sin(st)/2;
总面积只需再剩上他的边数就可以得到.....
代码如下:
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const double PI = 3.1415926535;
 6 const double esp=0.01;
 7 struct node{
 8   double x,y;
 9   //求两点之间的长度
10   double solen(node a){
11       return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
12   }
13 };
14 double dgcd(double a,double b)  //最小公倍数
15 {
16     if(a<esp) return b;
17     if(b<esp) return a;
18     return dgcd(b,fmod(a,b));
19 }
20 int main()
21 {
22   node a,b,c;
23   double rea,reb,rec,Area;
24   double angle[3];  //角度
25   //freopen("test.in","r",stdin);
26   scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
27         rea=a.solen(b);
28         reb=a.solen(c);
29         rec=b.solen(c);
30    //又海伦公式
31    double cc=(rea+reb+rec)/2.0;
32    Area=sqrt(cc*(cc-rea)*(cc-reb)*(cc-rec));
33   //求得外接圆半径r
34    double  rr=rea*reb*rec/(4*Area);
35    angle[0]=acos(1-rea*rea/(2*rr*rr));
36    angle[1]=acos(1-reb*reb/(2*rr*rr));
37    angle[2]=2*PI-angle[0]-angle[1];
38    //求出角之间的最大公约数
39    double ff=angle[0];
40    for(int i=1;i<3;i++)
41      ff=dgcd(ff,angle[i]);
42   //求得是多少边行
43    printf("%.6lf\n",(rr*rr*PI*sin(ff))/ff);
44   return 0;
45 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

39580
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

24180
来自专栏深度学习之tensorflow实战篇

tensorflow载入数据的三种方式 之 TF生成数据的方法

Tensorflow数据读取有三种方式: Preloaded data: 预加载数据 Feeding: Python产生数据,再把数据喂给后端。 Reading...

43640
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

26740
来自专栏算法修养

HOJ 2133&POJ 2964 Tourist(动态规划)

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503...

36780
来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.5K80
来自专栏计算机视觉与深度学习基础

Leetcode 132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a p...

221100
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

12930
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

13910
来自专栏数据结构与算法

欧拉函数详解

欧拉函数 我们用 表示欧拉函数 定义: 表示对于整数n,小于等于n中与n互质的数的个数 性质 1. 为积性函数 证明: 此处证明需要用到下面计算方法1中的...

32340

扫码关注云+社区

领取腾讯云代金券