【Atcoder】ARC082 E - ConvexScore

【算法】计算几何

【题意】给定平面直角坐标系上的若干个点，任意选点连成凸多边形，凸多边形的价值定义为2^(n-|S|)，其中n为凸多边形内部点数（含边界），|S|为顶点数，求总价值。n<=10^5。

【题解】

首先凸多边形的价值转化为凸多边形内部点数的选择方案（每个点选或不选）。

先考虑没有多点共线的情况。

本题中，对于每个方案，凸多边形外面没有点。①

对于一个若干点的图，只有唯一的凸多边形包括整个图。②

由上可知，①和②等价，也就是对于整个图枚举点选或不选的方案，唯一对应了一个答案，总价值为2^n-n^2-1（n为总点数，减去选0.1.2个点的方案）。

再来处理多点共线的情况，显然不能使选择的所有点都在同一直线上，所以枚举同一直线上的点数减去，细节见代码。

本题套路：枚举同一直线上的点，利用在同一直线上的点必定在其中两个点组成的直线上的原理，只需枚举任意两点，再枚举第三点是否在该直线上即可，复杂度O(1/6*n^3)。

题外套路：枚举多少直线交于一点，利用交于同一点的直线必然经过其中两条直线相交点的原理，直接枚举两条直线后再枚举第三条即可。

#include<cstdio>

int n,d,ans,x[],y[],p[];

int main(){

    scanf("%d",&n);

    int M=;

    p[]=;

    for(int i=;i<=n;i++){

        scanf("%d%d",&x[i],&y[i]);

        p[i]=1ll*p[i-]*%M;

    }

    ans=p[n]-n-;

    for(int i=;i<=n;i++){

        for(int j=i+;j<=n;j++){

            d=;

            for(int k=j+;k<=n;k++)d+=(y[i]-y[j])*(x[i]-x[k])==(y[i]-y[k])*(x[i]-x[j]);

            ans=(ans+M-p[d])%M;

        }

    }

    printf("%d",ans);

}