Codeforces

Luogu

分析

考虑任意五个点对答案的贡献。显然有

• 如果五个点的凸包为五边形，则贡献为 $0$；
• 如果五个点的凸包为四边形，则贡献为 $1$；
• 如果五个点的凸包为三角形，则贡献为 $2$。

我们只需要求出五个点凸包为为 $x$ 边形的方案数 $s_x$，然后答案即为 $s_4+2s_3$。

不知道怎么想到可以把答案拆成 $5(s_5+s_4+s_3)-(5s_5+4s_4+3_s3)$ 的形式，而又有 $s_5+s_4+s_3={n\choose 5}$，因此我们只需要计算 $5s_5+4s_4+3s_3$ 即可。这个东西的实际含义就是任意五个点的凸包所含的边数之和。

考虑枚举一条边并枚举它在多少个五个点的凸包中。我们先枚举一个点，然后把剩下的点极角排序并扫描（此时相当于枚举了一条边），则剩下 $3$ 个点都应在这条边左侧，每次找到范围后组合数算一下即可。

需要注意的是本题卡精度所以极角排序不能用 atan2，可以用叉积判断。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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;
}

const int N=2500+10;

int n,top,x[N],y[N];

struct Vector { int x,y; } sta[N<<1];
ll cross(Vector a,Vector b) { return 1ll*a.x*b.y-1ll*a.y*b.x; }
bool cmp(Vector a,Vector b) {
    int fa=a.y<0||(a.y==0&&a.x>0);
    int fb=b.y<0||(b.y==0&&b.x>0);
    return fa!=fb?fa<fb:cross(a,b)>0;
}

ll C(int n,int m) {
    if (n<m) return 0;
    ll res=1;
    for (int i=0;i<m;++i) res*=n-i,res/=i+1;
    return res;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    ll ans=C(n,5)*5;
    for (int i=1;i<=n;++i) {
        top=0;
        for (int j=1;j<=n;++j)
            if (i!=j) sta[++top]=(Vector){x[j]-x[i],y[j]-y[i]};
        sort(sta+1,sta+top+1,cmp);
        for (int j=1;j<=top;++j) sta[j+top]=sta[j];
        for (int j=1,p=1;j<=top;++j) {
            while (p<j+top&&cross(sta[j],sta[p])>=0) ++p;
            ans-=C(p-j-1,3);
        }
    }
    printf("%I64d\n",ans);
    return 0;
}