解題區/解題區 - UVa

UVa 11186 - Circum Triangle

contents

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

Problem

半徑為 R 的圓上有 N 個點，請問任挑三點形成的三角形面積總和為多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0

Sample Output

1
2
286
320

Solution

因此總共有 C(N, 3) 的三角形，聽說直接窮舉三點計算三角形面積就可以過，時間複雜度是 O(n^3)。事實上可以換個方式想，計算三角形面積，相當於用一個圓減去三個弓形面積。

那麼實際上會有 C(N, 3) 個圓減去一堆弓形面積。關於所有弓形面積的計算，可以窮舉兩點拉一條邊作為弦，接著會有兩個弓形，分別找到左右兩側的點數，就能知道有多少三角形分別使用多少次這些弓形面積，加總之後就是總共的弓形面積，複雜度降至 O(n^2)。

事實上還可以再更數學點，但是不太會推導，最後貌似可以在 O(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
44
45
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const double pi = acos(-1);
int main() {
    int N;
    double R, theta[512];
    while (scanf("%d %lf", &N, &R) == 2 && N) {
        for (int i = 0; i < N; i++) {
            scanf("%lf", &theta[i]);
            theta[i] = theta[i] * pi / 180;
        }
        sort(theta, theta+N);
        double ret = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int a = j - i - 1;
                int b = N - a - 2;
                double A, B, t = theta[j] - theta[i];
                A = t /2 * R * R - R * R * sin(t)/2;
                B = R * R * pi - A;
                ret += a * B + b * A;
//				printf("[%lf %lf] %lf %lf\n", theta[i], theta[j], A, B);
            }
        }
        ret = (double)(N) * (N-1) * (N-2) / 6 * R * R * pi - ret;
        if (N < 3)	ret = 0;
        printf("%.0lf\n", ret);
    }
    return 0;
}
/*
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0
*/