题目链接：uva
11529 - Strange Tax Calculation

题目大意：给出若干个点，保证随意三点不共线。随意选三个点作为三角行，其它点若又在该三角形内，则算是该三角形内部的点。问全部情况的三角形平均每一个三角形有多少个内部点。

解题思路：三角形的总数非常easy求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;

}