解題區/解題區 - UVa

UVa 11529 - Strange Tax Calculation

contents

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

Problem

任挑三個點拉出三角形，三角形內部的點數期望值為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0

Sample Output

1
2
City 1: 0.20
City 2: 0.20

Solution

反過來寫，這一點會被多少個三角形包含住。

為了要計算這一個點 P 被多少三角形包含住，把這個點 P 當作基礎點，對其他點做極角排序。排序完套用極角掃描線算法，對於當前線上的點 Q，往回追溯 180 度內，任挑兩個點與其並成三角形，保證不包含 P。

那麼要得到包含 P 的就反過來用全部組合扣到不包含的結果。

因為要窮舉每一點做極角排序，作法會在 O(n^2 log 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-9
const double pi = acos(-1);
struct Pt {
    double x, y;
    double angle;
    Pt(double a = 0, double b = 0):x(a), y(b) {
        angle = atan2(b, a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(angle - a.angle) > eps)
            return angle < a.angle;
        return false;
    }
}; 
long long C[1300][1300] = {};
long long getContainTriangle(int st, Pt D[], int n) {
    static Pt A[4096];
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == st)	continue;
        A[m++] = Pt(D[i].x - D[st].x, D[i].y - D[st].y);
    }
    sort(A, A + m);
    for (int i = 0; i < m; i++)
        A[i + m] = A[i], A[i+m].angle += 2 * pi;
    long long ret = 0;
    for (int i = 0, j = 1; i < m; i++) { // point(i, ?, ?)
        while (A[j].angle - A[i].angle <= pi - eps)	j++;
        ret += C[j - i - 1][2];
    }
    return C[m][3] - ret;
}
int main() {
    C[0][0] = 1;
    for (int i = 0; i < 1205; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    int n, cases = 0;
    Pt D[1500];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        long long contain = 0;// contain
        for (int i = 0; i < n; i++)
            contain += getContainTriangle(i, D, n); // with i-th point.
        printf("City %d: %.2lf\n", ++cases, (double)contain / C[n][3]);
    }
    return 0;
}
/*
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0
*/