解題區/解題區 - UVa

UVa 12300 - Smallest Regular Polygon

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Output for the Sample Input
  4. 4. Solution

Problem

二維平面中，給兩個點座標，以及一個 N，找到一個正 N 邊形，邊上通過這兩個點座標。求該正 N 邊形的最小面積為何？

Sample Input

1
2
3
4
0 0 1 1 4
1 2 3 4 5
2 3 4 5 6
0 0 0 0 0

Output for the Sample Input

1
2
3
1.000000
5.257311
5.196152

Solution

最小面積的正 N 邊形，保證通過兩點一定在正 N 邊行的兩個頂點，而不會出現在邊上。

分開討論奇偶數，奇數直接是對角線，偶數則偏離一點。找到兩點與圓心(正 N 邊形外接圓)拉出的三角形，根據張開的角度計算外接圓的半徑即可。

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
#include <stdio.h>
#include <math.h>
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
    int read() {
    	return scanf("%lf %lf", &x, &y);
    }
};
int main() {
    Pt A, B;
    const double pi = acos(-1); 
    int n;
    while(true) {
        A.read(), B.read(), scanf("%d", &n);
        if(n == 0)	break;
        double r, dist = hypot(A.x - B.x, A.y - B.y);
        if(n%2 == 0) {
            r = dist /2;
        } else {
            int m = (n - 1)/2;
            r = dist /2 / sin((double)m/2.0/n * 2 * pi);
        }
        printf("%lf\n", r * r * sin(2 * pi/n) * n/2);
    }
    return 0;
}