Submission #1870020


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=210,O=998244353;
template<class T>inline T sqr(T x){return x*x;}
struct Pt{
	int x,y;
}pt[N],pt2[N],base;
inline bool ycmp(const Pt &a,const Pt &b){
	return a.y!=b.y?a.y<b.y:a.x<b.x;
}
inline int cross(const Pt &a,const Pt &b){
	return (a.x-base.x)*(b.y-base.y)-(a.y-base.y)*(b.x-base.x);
}
inline bool polarcmp(const Pt &a,const Pt &b){
	int crs=cross(a,b);
	return crs?crs>0:sqr(a.x-base.x)<sqr(b.x-base.x);
}
int pw2[N];
inline void gmath(int n){
	pw2[0]=1;
	for(int i=1;i<=n;i++){
		pw2[i]=(lint)pw2[i-1]*2%O;
	}
}
int main(){
	int n=ni;
	gmath(n);
	for(int i=1;i<=n;i++){
		pt[i]=(Pt){ni,ni};
	}
	sort(pt+1,pt+n+1,ycmp);
	lint sum=1;
	for(int i=1;i<=n;i++){
		base=pt[i];
		memcpy(pt2+i+1,pt+i+1,(n-i)*sizeof(Pt));
		sort(pt2+i+1,pt2+n+1,polarcmp);
		for(int j=i+1,k=j;j<=n;j=k){
			for(;k<=n&&cross(pt2[j],pt2[k])==0;k++);
			sum+=pw2[k-j]-1;
		}
		sum++;//single
	}
	printf("%lld\n",((pw2[n]-sum%O)%O+O)%O);
	return 0;
}

Submission Info

Submission Time
Task E - ConvexScore
User acha
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1558 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 36
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 2 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 2 ms 256 KB
1_008.txt AC 2 ms 256 KB
1_009.txt AC 2 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 2 ms 256 KB
1_012.txt AC 2 ms 256 KB
1_013.txt AC 2 ms 256 KB
1_014.txt AC 1 ms 256 KB
1_015.txt AC 2 ms 256 KB
1_016.txt AC 1 ms 256 KB
1_017.txt AC 2 ms 256 KB
1_018.txt AC 2 ms 256 KB
1_019.txt AC 2 ms 256 KB
1_020.txt AC 2 ms 256 KB
1_021.txt AC 2 ms 256 KB
1_022.txt AC 2 ms 256 KB
1_023.txt AC 2 ms 256 KB
1_024.txt AC 2 ms 256 KB
1_025.txt AC 2 ms 256 KB
1_026.txt AC 2 ms 256 KB
1_027.txt AC 2 ms 256 KB
1_028.txt AC 2 ms 256 KB
1_029.txt AC 2 ms 256 KB
1_030.txt AC 2 ms 256 KB
1_031.txt AC 2 ms 256 KB
1_032.txt AC 2 ms 256 KB
1_033.txt AC 2 ms 256 KB
1_034.txt AC 2 ms 256 KB
1_035.txt AC 2 ms 256 KB