ComplexCode/uva11529.cpp at master · Mithril0rd/ComplexCode · GitHub

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAX_N = 1207;
const double PI = acos(-1.);

struct Point {
	double x, y;
};

int n;
double ox[MAX_N<<1];
Point p[MAX_N];

long long C3(int n) {
	return (long long)n * (n - 1) / 2 * (n - 2) / 3;
}

long long C2(int n) {
	return (long long)n * (n - 1) / 2;

}

long long cal() {
	long long all = C3(n - 1);
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int cnt = 0;
		for (int j = 0; j < n; ++j) {
			if (j == i)
			  continue;
			double at = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
			ox[cnt++] = at;
		}
		sort(ox, ox + cnt);
		int cnt1 = cnt;
		for (int j = 0; j < cnt1; ++j) {
			ox[cnt++] = ox[j] + 2 * PI;
		}
		int now = 0;
		long long count = 0;
		for (int j = 0; j < cnt1; ++j) {
			while (ox[now] < ox[j] + PI)
			  ++now;
			count += C2(now - j - 1);
		}
		ans += all - count;
	}
	return ans;
}

int main() {
	int cas = 0;
	while (1 == scanf("%d", &n)) {
		if (0 == n)
		  break;
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf", &p[i].x, &p[i].y);
		}
		double ans = 1. * cal() / C3(n);
		printf("City %d: %.2f\n", ++cas, ans);
	}
	return 0;
}