多边形求最小面积

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目：Ancient Berland Circus

题意：给你一个正凸多边形的三个点，然后求出这个正凸多边形的面积的最小值。

方法是这样的：以这三个点做一个三角形，求出这个三角形的外心（外接圆的圆心），这个点也就是外接多边形的中心

然后找出内角所对应的边数的GCD

当然，内角所对应的边数不一定是整数，我们需要用double的GCD和LCM进行计算，求出最小边数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <stack>
using namespace std;
 
const double PI = acos(-1.0);
const double eps = 1e-4;
 
//浮点数的GCD
double gcd(double x, double y)
{
    while(fabs(x) > eps && fabs(y) > eps)
    {
        if(x > y)
            x -= floor(x/y)*y;
        else
            y -= floor(y/x)*x;
    }
    return x+y;
}
 
double a_cos(double a, double b, double c)
{
    return acos((a*a+b*b-c*c)/(2*a*b));
}
 
int main()
{
    //freopen("aa.in", "r", stdin);
    //freopen("bb.out", "w", stdout);
 
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
    double a = sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
    double b = sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
    double c = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    double A = a_cos(b, c, a);
    double B = a_cos(a, c, b);
    double C = a_cos(a, b, c);
    double P = (a + b + c) / 2;
    double S = sqrt(P*(P-a)*(P-b)*(P-c));
    double R = (a*b*c)/(4*S);
    double N = PI/gcd(A, gcd(B, C));
    printf("%.8lf\n", 0.5*R*R*sin(2*PI/N)*N);
    return 0;
}

原文