Submission #1564336

---

Source Code Expand

//no convex hull ans=0.
//S:convex polygon counted:2^(n-|S|)
//number of subsets.
//U:inside S(\S) 
//S union U: convex hull is S
//number of pair:(S,U),where the convex hull of S union U is S
//S union U corresponds to a unique S,thus a unique U
//bijection (S,U)<->S union U
//for each subset of set,it is valid if the convex hull exists.(has postive area)
//the only case is colinear!
//ans=2^n-1-C(n,1)-C(n,2)-sigma(2^ai-ai-C(ai,2)-1)(ai>=3)
#include<cstdio>
#include<algorithm>
using namespace std;
bool vis[210][210];
struct kk
{
	int id;
	double num;
}c[210];
int n,i,j,k,l,x[210],y[210];
long long pow2[210],ans;
const long long P=998244353;
bool cmp(kk A,kk B)
{
	return A.num<B.num;
}
int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	pow2[0]=1;
	for (i=1;i<=n;i++) pow2[i]=pow2[i-1]*2%P;
	ans=pow2[n];
	ans-=1+n+n*(n-1)/2;
	ans=(ans%P+P)%P;
	for (i=1;i<n;i++)
	{
		int tot=0;
		for (j=i+1;j<=n;j++)
		{
			if (vis[i][j]) continue;
			int dx=x[j]-x[i],dy=y[j]-y[i];
			if (dx==0) 
			{
				c[++tot].id=j;
				c[tot].num=100000;
			}
			else
			{
				c[++tot].id=j;
				c[tot].num=(double)dy/(double)dx;
			}
		}
		if (tot==0) continue;
		sort(c+1,c+tot+1,cmp);
		c[0].num=c[1].num-1;
		long long now=0;
		for (int j=1;j<=tot;j++)
		{
			if (c[j].num-c[j-1].num<1e-8) now++;
			else
			{
				for (k=j-now;k<j;k++)
				  for (l=k+1;l<j;l++)
				  {
				  	vis[c[k].id][c[l].id]=1;
				  	vis[c[l].id][c[k].id]=1;
				  }
				now++;//itself;
				if (now>=3) ans-=pow2[now]-now-now*(now-1)/2-1;
				now=1;
				ans=(ans%P+P)%P;
			}
		}
		for (k=tot-now+1;k<=tot;k++)
			for (l=k+1;l<=tot;l++)
				{
				  	vis[c[k].id][c[l].id]=1;
				  	vis[c[l].id][c[k].id]=1;
				}
		now++;
		if (now>=3) ans-=pow2[now]-now-now*(now-1)/2-1;
		ans=(ans%P+P)%P;
	}
	printf("%lld\n",ans);
}
//O(n^2 logn)

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:31:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
                                              ^

Judge Result