UVa

Luogu

分析

一道不错的数数题。

首先可以知道，三角形总数是 $n\choose 3$ ，所以只需要求出所有三角形包含的点数之和即可。

可以转化一下，变成求每个点被多少个三角形包含。

这个东西等于 $n-1\choose 3$ 减去不包含这个点的三角形个数。

于是我们重点考虑怎么求不包含一个点 $x$ 的三角形个数。

把除了 $x$ 之外的所有点拿出来，按极角序排序后扫描。假设当前扫到了 $i$ ，那么极角在 $(ang_i,ang_i+\pi)$ 范围内的点与 $i$ 组成的三角形都不包含 $x$ 。拿一个指针维护即可。

然后因为会绕一周，所以要把所有极角加上 $2\pi$ 后接在后面，方便处理。

可以发现这样子计数是不重不漏的。于是这题就做完了。

单组数据时间复杂度 $O(n^2)$ 。另外注意要开 long long 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

inline int C2(int x) { return x*(x-1)/2; }
inline int C3(int x) { return x*(x-1)*(x-2)/6; }

const int N=1200+10;

int n;
struct Point { int x,y; } p[N];
double sta[N<<1]; int top=0;

inline int calc2(int x) {
    top=0;
    for (re int i=1;i<=n;++i) {
        if (i==x) continue;
        double ang=atan2(p[i].y-p[x].y,p[i].x-p[x].x);
        sta[++top]=ang,sta[++top]=ang+2*M_PI;
    }
    sort(sta+1,sta+top+1);
    int ans=0;
    for (re int i=1,j=1;i<n;++i) {
        while (sta[j]<sta[i]+M_PI) ++j;
        ans+=C2(j-i-1);
    }
    return ans;
}

inline int calc() {
    int ans=0;
    for (re int i=1;i<=n;++i) ans+=C3(n-1)-calc2(i);
    return ans;
}

signed main() {
    int _=0;
    while (n=read()) {
        for (re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
        printf("City %d: %.2lf\n",++_,1.0*calc()/C3(n));
    }
    return 0;
}