[arc082E]ConvexScore-[凸包]

Description

传送门

Solution

em又是神仙题。

考虑到目前的一个凸包，顶点点集为S。

现在在它内部或边缘上的点集为T，则贡献为 $2^{m - | S |}$ ^{$2^{m - | S |}$} $2^{m - | S |}$

$2^{m - | S |}$

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n;
ll pw[210],ans=0;
struct node{int x,y;
}p[210];
bool check(node a,node b,node c)
{ return (b.x-a.x)*(c.y-a.y)==(b.y-a.y)*(c.x-a.x);}
void link(int x,int y){x+=y;}
int main()
{
    link(0,1);
    scanf("%d",&n);
    pw[0]=1;
    for (int i=1;i<=n;i++) pw[i]=(pw[i-1]<<1)%mod;    
    for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
    
    ans=(pw[n]-n-1+mod)%mod;bool _is;int cnt;
    for (int i=1;i<n;i++) 
        for (int j=i+1;j<=n;j++)
        {
            _is=1;
            for (int k=1;k<i;k++) if (check(p[k],p[i],p[j])) {_is=0;break;}
            for (int k=i+1;k<j;k++) if (check(p[k],p[i],p[j])) {_is=0;break;}
            if (!_is) continue;
            cnt=2;
            for (int k=j+1;k<=n;k++) if (check(p[k],p[i],p[j])) cnt++;
            ans=(ans-pw[cnt]+cnt+1+mod)%mod;
        }
    cout<<ans;
}

$2^{m - | S |}$