Submission #1815487
Source Code Expand
#include <cstdio>
#include <cstring>
#define MAXN 210
#define LL long long
const LL P=998244353;
LL getPow(LL x,LL y){
LL res=1;
while(y){
if(y&1) res=res*x%P;
x=x*x%P;
y>>=1;
}
return res;
}
struct vec2{
int x,y;
vec2(int _x=0,int _y=0):x(_x),y(_y){}
friend vec2 operator-(vec2 x,vec2 y){ return vec2(x.x-y.x,x.y-y.y); }
friend int dot(vec2 x,vec2 y){ return x.x*y.x+x.y*y.y; }
friend int cross(vec2 x,vec2 y){ return x.x*y.y-x.y*y.x; }
}p[MAXN];
int n;
int main(){
#ifdef DEBUG
freopen("E.in","r",stdin);
#endif
LL inv2=getPow(2,P-2);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
LL ans=getPow(2,n);
LL res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i^j){
vec2 d=p[j]-p[i];
int cnt=2;
for(int k=1;k<=n;k++)
if(cross(p[k]-p[j],d)==0 && k!=i && k!=j){
if(dot(p[k]-p[j],d)<0){
cnt=0;
break;
}
cnt++;
}
LL temp=getPow(2,cnt)-cnt-1;
res=(res+temp)%P;
}
res=res*inv2%P;
res=(res+n+1)%P;
ans-=res;
ans=(ans%P+P)%P;
printf("%lld\n",ans);
}
Submission Info
Submission Time |
|
Task |
E - ConvexScore |
User |
ez_zjt |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1125 Byte |
Status |
AC |
Exec Time |
11 ms |
Memory |
128 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:33:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:34:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
^
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 |
128 KB |
0_001.txt |
AC |
1 ms |
128 KB |
0_002.txt |
AC |
1 ms |
128 KB |
1_003.txt |
AC |
1 ms |
128 KB |
1_004.txt |
AC |
1 ms |
128 KB |
1_005.txt |
AC |
3 ms |
128 KB |
1_006.txt |
AC |
1 ms |
128 KB |
1_007.txt |
AC |
5 ms |
128 KB |
1_008.txt |
AC |
3 ms |
128 KB |
1_009.txt |
AC |
4 ms |
128 KB |
1_010.txt |
AC |
1 ms |
128 KB |
1_011.txt |
AC |
5 ms |
128 KB |
1_012.txt |
AC |
6 ms |
128 KB |
1_013.txt |
AC |
3 ms |
128 KB |
1_014.txt |
AC |
1 ms |
128 KB |
1_015.txt |
AC |
1 ms |
128 KB |
1_016.txt |
AC |
1 ms |
128 KB |
1_017.txt |
AC |
11 ms |
128 KB |
1_018.txt |
AC |
11 ms |
128 KB |
1_019.txt |
AC |
8 ms |
128 KB |
1_020.txt |
AC |
8 ms |
128 KB |
1_021.txt |
AC |
9 ms |
128 KB |
1_022.txt |
AC |
9 ms |
128 KB |
1_023.txt |
AC |
10 ms |
128 KB |
1_024.txt |
AC |
10 ms |
128 KB |
1_025.txt |
AC |
9 ms |
128 KB |
1_026.txt |
AC |
9 ms |
128 KB |
1_027.txt |
AC |
1 ms |
128 KB |
1_028.txt |
AC |
1 ms |
128 KB |
1_029.txt |
AC |
9 ms |
128 KB |
1_030.txt |
AC |
11 ms |
128 KB |
1_031.txt |
AC |
11 ms |
128 KB |
1_032.txt |
AC |
11 ms |
128 KB |
1_033.txt |
AC |
11 ms |
128 KB |
1_034.txt |
AC |
11 ms |
128 KB |
1_035.txt |
AC |
7 ms |
128 KB |