ARC082C ConvexScore

简要题意

给定n个点，定义一个凸多边形包含点数s为：这个凸多边形覆盖的点数-这个凸多边形的角数（每一个角\(<180°\))

设总点集为A。 这个凸多边形的分值为为：\(2^s\)

求由这n个点构成的所有凸多边形的分值和\(mod 998244353\) ### 简要题解 \(2^s\)是这s个点可选可不选的总方案数。 则答案是\(\sum_{s\subset A}[s构成一个凸多边形]\sum_{t子集内的点被s多边形覆盖}1\)

令\(S=s\cup t\) 我们可以直接枚举\(S\)。当\(S\)内的点不构成一条线段或只有一个点的时候，它有唯一的一个凸包，则它对答案的贡献就为1。

首先我们先不考虑线段，则答案为\(2^n-n-1\)（每个点选或不选-单点-空集） 接着我们找出每一条线段（点数\(>1\))，对于每条线段，假如有m个点，则它对答案的减少就为\(2^m-m-1\)（每个点选或不选-单点和空集没有之前已经去掉了） ### 简要代码

/*
Author: CNYALI_LK
LANG: C++
PROG: E.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
const ll mod=998244353;
ll p[233];
struct zb{
    ll x,y;
};
zb a[233];
ll cmp(zb a,zb b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ll n,ans;
    scanf("%lld",&n);
    p[0]=1;
    for(ll i=1;i<=n;++i){p[i]=p[i-1]<<1;if(p[i]>=mod)p[i]-=mod;scanf("%lld%lld",&a[i].x,&a[i].y);}
    sort(a+1,a+n+1,cmp);
    ans=p[n]-n-1;
    for(ll i=1;i<=n;++i)for(ll j=i+1;j<=n;++j){
        ll no=0;
        for(ll k=1;k<j;++k)if(k!=i&&(a[j].x-a[i].x)*(a[i].y-a[k].y)==(a[j].y-a[i].y)*(a[i].x-a[k].x)){no=1;break;}
        if(!no){
///         debug("(%lld,%lld) (%lld,%lld)",a[i].x,a[i].y,a[j].x,a[j].y);
            ll tot=2;
            for(ll k=j+1;k<=n;++k){
                if((a[j].x-a[i].x)*(a[i].y-a[k].y)==(a[j].y-a[i].y)*(a[i].x-a[k].x)){++tot;/*debug(" (%lld,%lld)",a[k].x,a[k].y);*/}
            }
//          debug("\n");
            ans-=p[tot]-tot-1;
        }
    }   
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}