【ARC082E】Convex Score【枚舉】

考慮一個有 n n n個頂點凸多邊形，多邊形内（包括頂點）有 k k k個點，則會造成 2 k − n 2^{k-n} 2k−n的貢獻。我們可以轉化一下， k − n k-n k−n其實就是凸多邊形内部的點的數量， 2 k − n 2^{k-n} 2k−n就是這些點每個都可以取或者不取的方案數。是以我們就可以把問題轉化一下：有多少種選點的方案，使得這些點圍起來是一個凸多邊形。

考慮怎樣的情況，這些點圍起來不是一個凸多邊形，那一定是出現了三點共線。是以我們可以容斥。用所有方案減去出現三點共線的方案數。

設有 n n n個點。則所有方案為 2 n − n ∗ ( n + 1 ) 2 − n − 1 2^n-\frac{n*(n+1)}{2}-n-1 2n−2n∗(n+1)​−n−1。因為 0 0 0個點， 1 1 1個點， 2 2 2個點都不可能出現凸多邊形。

接下來我們可以枚舉某一條邊，再求出有多少個點在這條邊上。設答案為 n n n，則中間的點可以随便選，但要去掉一個點都不選的方案。是以減去的貢獻為 2 n − 1 2^n-1 2n−1。

怎麼判斷三點是否共線？斜率判一判就好。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 998244353
using namespace std;
const int N=205;
int n,ans,fastpow[N],x[N],y[N];
inline int rd(){
	register char ch=getchar();
	register int res=0;
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=res*10+ch-'0';
		ch=getchar();
	}
	return res;
}
int main(){
	n=rd();
	fastpow[0]=1;
	for(register int i=1;i<=n;++i){
		x[i]=rd(),y[i]=rd();
		fastpow[i]=fastpow[i-1]*2%mod;
	}
	ans=(fastpow[n]-n-n*(n-1)/2-1)%mod;
	for(int i=2;i<=n;i++){
		for(register int j=i+1;j<=n;++j){
			int tot=0;
			for(register int k=1;k<i;++k){
				if((x[i]-x[j])*(y[j]-y[k])==(y[i]-y[j])*(x[j]-x[k])){
					tot++;
				}
			}
			ans=(ans-fastpow[tot]+1)%mod;
		}
	}
	printf("%d\n",(ans+mod)%mod);
	return 0;
}