枚举一个中心点，然后将其他点绕着这个点按照极角排序。
统计这个中心点在外面的三角形的个数，然后用C(n-1, 3)减去这个数就是包含这个点的三角形的数量。
然后再枚举一个起点L，终点为弧度小于π的点R。
在[L+1, R]任取两点再加上起点，这些三角形都不包含中心点。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 1200 + 10; 7 const double PI = acos(-1.0); 8 9 struct Point 10 { 11 int x, y; 12 }p[maxn]; 13 double ang[maxn * 2]; 14 typedef Point Vector; 15 16 double inline C2(int n) { return n * (n-1) / 2; } 17 double inline C3(int n) { return n * (n-1) / 2 * (n-2) / 3; } 18 double solve(int n) 19 { 20 double s = C3(n-1), ans = 0; 21 for(int i = 0; i < n; i++) 22 {//枚举中心点 23 int k = 0; 24 for(int j = 0; j < n; j++) if(j != i) 25 { 26 ang[k] = atan2(p[j].x-p[i].x, p[j].y-p[i].y); 27 ang[k + n - 1] = ang[k] + 2.0 * PI; 28 k++; 29 } 30 k = 2*(n-1); 31 sort(ang, ang + k); 32 int L = 0, R = 0; 33 double t = 0; 34 for(L = 0; L < n-1; L++) 35 { 36 double temp = ang[L] + PI; 37 while(temp > ang[R]) R++; 38 t += C2(R - L - 1); 39 } 40 ans += s - t; 41 } 42 return ans; 43 } 44 45 int main() 46 { 47 //freopen("in.txt", "r", stdin); 48 49 int n, kase = 0; 50 while(scanf("%d", &n) == 1 && n) 51 { 52 for(int i = 0; i < n; i++) 53 scanf("%d%d", &p[i].x, &p[i].y); 54 double ans = solve(n) / C3(n); 55 printf("City %d: %.2f ", ++kase, ans); 56 } 57 58 return 0; 59 }