首页 > 其他 > 详细

CodeForces 1C Ancient Berland Circus

时间:2015-07-29 22:44:31      阅读:382      评论:0      收藏:0      [点我收藏+]

题意:给定三个点,求包含三点的正多边形最小面积;

思路:求圆心角最大公约数,多边形面积=每个小三角形面积和;

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string>
#include<map>
#include<iostream>
using namespace std;
#define eps 1e-2
#define pi acos(-1.0)
int n,m;
double s,r,S,p;
double x[4],y[4],ang[4],L[5];
double dis(double x1,double y1,double x2,double y2){
   return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double gcd(double a,double b)
{
    if(a<eps) return b;
    if(b<eps) return a;
    return gcd(b,fmod(a,b));
}
int main()
{
    int i,j,k;
    for(i=0;i<3;i++){
      scanf("%lf%lf",&x[i],&y[i]);
    }
    for(i=0;i<3;i++){
      L[i]=dis(x[i],y[i],x[(i+1)%3],y[(i+1)%3]); //求距离
    }
    p=(L[0]+L[1]+L[2])/2; 
    s=sqrt(p*(p-L[0])*(p-L[1])*(p-L[2])); //海伦凯勒公式求面积
    r=L[0]*L[1]*L[2]/(4*s); //外接圆半径
    for(i=0;i<3;i++) ang[i]=acos(1-L[i]*L[i]/(2*r*r));
    ang[2]=2*pi-ang[1]-ang[0]; //三个圆心角,余弦定理
    double unit=0;
    for(i=0;i<3;i++) unit=gcd(unit,ang[i]); //圆心角的最大公约数
    printf("%.6f\n",pi*r*r*sin(unit)/unit); //2*pi/unit为个数,S为每个三角形面积
    return 0;
}

 

CodeForces 1C Ancient Berland Circus

原文:http://www.cnblogs.com/dominatingdashuzhilin/p/4687349.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!