Submission #1566510
Source Code Expand
#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
const double EPS = 1e-12;
typedef complex<long double> P;
namespace std {
bool operator < (const P& a, const P& b) {
return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}
double cross(const P& a, const P& b) {
return imag(conj(a)*b);
}
struct L : public vector<P> {
L(const P &a, const P &b) {
push_back(a); push_back(b);
}
};
bool intersectLP(const L &l, const P &p) {
return abs(cross(l[1]-p, l[0]-p)) < EPS;
}
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<pair<int,int> >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&&intersectLP(l,v[k]))x.push_back(k);
for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
int n=b-a-1;
r=(r-pow_binary_mod(2,n,M))%M;
se.emplace(x[a],x[b]);
}
}
printf("%d\n",((r-N-1)%M+M)%M);
}
Submission Info
Submission Time
2017-09-03 18:33:07+0900
Task
E - ConvexScore
User
leafmoon
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
1448 Byte
Status
AC
Exec Time
143 ms
Memory
1152 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:44:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
./Main.cpp:48: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
2 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
36 ms
640 KB
1_006.txt
AC
1 ms
256 KB
1_007.txt
AC
41 ms
768 KB
1_008.txt
AC
26 ms
640 KB
1_009.txt
AC
37 ms
768 KB
1_010.txt
AC
10 ms
384 KB
1_011.txt
AC
53 ms
768 KB
1_012.txt
AC
66 ms
896 KB
1_013.txt
AC
33 ms
640 KB
1_014.txt
AC
1 ms
256 KB
1_015.txt
AC
4 ms
896 KB
1_016.txt
AC
2 ms
512 KB
1_017.txt
AC
143 ms
1152 KB
1_018.txt
AC
143 ms
1152 KB
1_019.txt
AC
73 ms
1152 KB
1_020.txt
AC
70 ms
1152 KB
1_021.txt
AC
84 ms
1152 KB
1_022.txt
AC
103 ms
1152 KB
1_023.txt
AC
125 ms
1152 KB
1_024.txt
AC
124 ms
1152 KB
1_025.txt
AC
114 ms
1152 KB
1_026.txt
AC
114 ms
1152 KB
1_027.txt
AC
6 ms
1152 KB
1_028.txt
AC
6 ms
1152 KB
1_029.txt
AC
114 ms
1152 KB
1_030.txt
AC
137 ms
1152 KB
1_031.txt
AC
138 ms
1152 KB
1_032.txt
AC
137 ms
1152 KB
1_033.txt
AC
138 ms
1152 KB
1_034.txt
AC
141 ms
1152 KB
1_035.txt
AC
78 ms
1152 KB