题目链接

题意简述

平面上有$n$个点，对于每一个顶点都是这$n$个点的凸多边形，都会对答案产生2x2^x2x的贡献，其中$x$为凸多边形内部点的个数，包括在边上的点，但是不包括顶点。求答案模$998244353$。

题解

观察贡献的特点，可以发现每个凸多边形对答案的贡献就是凸包为这个凸多边形的点集个数，那么答案就是能构成凸包的点集个数，也就是所有点集$-$共线点集个数。统计共线点集可以O(n3)O(n^3)O(n3)也可以O(n2log⁡n)O(n^2\log n)O(n2logn)。下面代码用O(n3)O(n^3)O(n3)的方法。（我才不告诉你我不会O(n2log⁡n)O(n^2\log n)O(n2logn)呢QwQ）

代码

#include 
    
     int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=200;const int mod=998244353;struct point{
      int x,y;};point p[maxn+10];int n,ans;int quickpow(int a,int b,int m){
      int res=1;  while(b)    {
          if(b&1)        {
              res=1ll*res*a%m;        }      a=1ll*a*a%m;      b>>=1;    }  return res;}int in_line(point a,point b,point c){
      return (b.y-a.y)*(c.x-a.x)==(c.y-a.y)*(b.x-a.x);}int main(){
      n=read();  for(int i=1; i<=n; ++i)    {
          p[i].x=read();      p[i].y=read();    }  for(int i=1; i<=n; ++i)    {
          for(int j=i+1; j<=n; ++j)        {
              int cnt=0;          for(int k=j+1; k<=n; ++k)            {
                  if(in_line(p[i],p[j],p[k]))                {
                      ++cnt;                }            }          ans+=quickpow(2,cnt,mod);          if(ans>=mod)            {
                  ans-=mod;            }        }    }  ans+=n+1;  if(ans>=mod)    {
          ans-=mod;    }  ans=quickpow(2,n,mod)-ans;  if(ans<0)    {
          ans+=mod;    }  printf("%d\n",ans);  return 0;}