【AtCoder Regular Contest 082 E】ConvexScore | Mrsrz's blog

计算几何，数学。

题目大意：

给定平面上 $n$ 个点。从这些点中选择一些能构成凸包的点形成点集 $S$（必须都是顶点且内角小于 $180^\circ$）。

假设点集 $S$ 形成的凸包的内部、边上、顶点上共有 $k$ 个点，则 $S$ 的贡献为 $2^{k-|S|}$。

求所有这样的点集的贡献和。

题解：

考虑 $S$ 点集内部、边上的点形成的点集为 $T$，则 $S$ 的贡献为 $2^{|T|}$。这个的含义其实是 $T$ 的子集个数。

因此，相当于 $S$ 和 $T$ 中的任意一个子集的并集产生了 $1$ 的贡献。

由于一个点集的凸包是唯一的，所以这个贡献和其实相当于有凸包的点集的个数和。

我们考虑一个点集什么时候不存在凸包。仅当这些点都在同一直线上时，无法形成凸包。

一开始的总方案为 $2^n-n-1-\binom{n}{2}$（顶点任意选择，去掉 $0,1,2$ 个点的情况）。

然后我们考虑枚举两个点，确定一条直线，然后再枚举得到这条直线上还有的其它点个数 $t$，这些点任选都是不合法的，所以减去 $2^{t}-1$。

时间复杂度 $O(n^3)$。

Code：

#include<cstdio>
const int N=233,md=998244353;
struct point{
    int x,y;
    inline point operator-(const point&rhs)const{return(point){x-rhs.x,y-rhs.y};}
}a[N];
inline int cross(point a,point b){return a.x*b.y-a.y*b.x;}
int n,p2[N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=*p2=1;i<=n;++i)p2[i]=p2[i-1]*2%md;
    ans=(p2[n]-n-1LL-n*(n-1LL)/2%md+md*4LL)%md;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j){
            int x=0;
            for(int k=j+1;k<=n;++k)
                x+=!cross(a[j]-a[i],a[k]-a[i]);
            ans=(ans-p2[x]+1+md)%md;
        }
    printf("%d\n",ans);
    return 0;
}