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 |
|
|
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 |