题目
https://vjudge.net/problem/UVA-11529
题意
给出若干个点，保证任意三点不共线，任意选三个点作为三角行，其他点若又在该三角形内，则算是该三角形内部的点，问所有情况的三角形平均每个三角形有多少个内部点。
思路
三角形的总数很容易求C(3n),现在就是要求各个三角形内部点的总数，同样我们可以反过来，求每个点在多少个三角形的内部。
然后我们确定一个点，求该点在多少个三角的内部，剩余n-1个点，可以组成C(3n?1])个三角形，所以只要求出该点在哪些三角形的外部即可。
红色点为选中的点，将周围点按照与选中点的极角进行排序，每次枚举一点，它的极角为a，所有极角小于a+pi的点，这些点组成的三角形，选中点一定在外部。处理一周的方式是将点的数组扩大两倍，将所有点的极角加上pi有保留在延长的数组中。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
const int N = 1205;
const double pi = 4 * atan(1.0);
const double eps = 1e-9;int n;
double s, r[2*N];
struct point {double x, y;
}p[N];double Count (int d) {int c = 0, mv = 0;for (int i = 0; i < n; i++) {if (i == d)continue;double a = atan2(p[i].y-p[d].y, p[i].x-p[d].x);r[c] = a;r[c+n-1] = a + 2*pi;c++;}c = 2 * n - 2;sort(r, r + c);double ans = 0;for (int i = 0; i < n-1; i++) {double tmp = r[i] + pi;while (tmp > r[mv])mv++;double cnt = mv - i - 1;ans = ans + cnt * (cnt-1) / 2;}return s - ans;
}double solve () {s = (n-1) * (n-2) * (n-3) / 6.0;double c = n * (n-1) * (n-2) / 6.0;double ans = 0;for (int i = 0; i < n; i++)ans += Count(i);return ans / c;
}int main () {int cas = 1;while (scanf("%d", &n) == 1 && n) {for (int i = 0; i < n; i++)scanf("%lf%lf", &p[i].x, &p[i].y);printf("City %d: %.2lf\n", cas++, solve());}return 0;
}