Submission #1566270
Source Code Expand
#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
const double EPS = 1e-12;
typedef complex<long double> P;
struct L : public vector<P> {
L(const P &a, const P &b) {
push_back(a); push_back(b);
}
};
bool intersectSP(const L &s, const P &p) {
return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}
long long pow_binary_mod(long long x,long long y,long long M){
long long z=1;
for(;y;y>>=1){
if((y&1)!=0)z=z*x%M;
x=x*x%M;
}
return z;
}
int main(){
int M=998244353;
int N,x,y;
scanf("%d",&N);
vector<P>v(N);
int r=pow_binary_mod(2,N,M);
set<L>se;
for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
//if(se.find({i,j})!=se.end())continue;
L l(v[i],v[j]);
vector<int>x={i,j};
for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectSP(l,v[k]))x.push_back(k);
r=(r-pow_binary_mod(2,x.size()-2,M))%M;
for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
//se.emplace(x[a],x[b]);
}
}
printf("%d\n",((r-N-1)%M+M)%M);
}
Submission Info
Submission Time
2017-09-03 17:16:14+0900
Task
E - ConvexScore
User
leafmoon
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
1122 Byte
Status
AC
Exec Time
600 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:31:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
./Main.cpp:35:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)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
3 ms
384 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
144 ms
256 KB
1_006.txt
AC
1 ms
256 KB
1_007.txt
AC
288 ms
256 KB
1_008.txt
AC
176 ms
256 KB
1_009.txt
AC
223 ms
256 KB
1_010.txt
AC
41 ms
256 KB
1_011.txt
AC
202 ms
256 KB
1_012.txt
AC
256 ms
256 KB
1_013.txt
AC
135 ms
256 KB
1_014.txt
AC
2 ms
256 KB
1_015.txt
AC
243 ms
256 KB
1_016.txt
AC
70 ms
256 KB
1_017.txt
AC
587 ms
256 KB
1_018.txt
AC
587 ms
256 KB
1_019.txt
AC
583 ms
256 KB
1_020.txt
AC
570 ms
256 KB
1_021.txt
AC
584 ms
256 KB
1_022.txt
AC
585 ms
256 KB
1_023.txt
AC
500 ms
256 KB
1_024.txt
AC
499 ms
256 KB
1_025.txt
AC
493 ms
256 KB
1_026.txt
AC
491 ms
256 KB
1_027.txt
AC
455 ms
256 KB
1_028.txt
AC
451 ms
256 KB
1_029.txt
AC
568 ms
256 KB
1_030.txt
AC
578 ms
256 KB
1_031.txt
AC
579 ms
256 KB
1_032.txt
AC
575 ms
256 KB
1_033.txt
AC
580 ms
256 KB
1_034.txt
AC
516 ms
256 KB
1_035.txt
AC
600 ms
256 KB