Submission #1555295
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<unsigned int mod_>
struct ModInt{
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr static uint mod = mod_;
uint v;
ModInt():v(0){}
ModInt(ll v):v(normS(v%mod+mod)){}
explicit operator bool() const {return v!=0;}
static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1]
static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
ModInt operator-() const { return make(normS(mod-v)); }
ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
ModInt operator/(const ModInt& b) const { return *this*b.inv();}
ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
ll extgcd(ll a,ll b,ll &x,ll &y) const{
ll u[]={a,1,0},v[]={b,0,1};
while(*v){
ll t=*u/ *v;
rep(i,3) swap(u[i]-=t*v[i],v[i]);
}
if(u[0]<0) rep(i,3) u[i]=-u[i];
x=u[1],y=u[2];
return u[0];
}
ModInt inv() const{
ll x,y;
extgcd(v,mod,x,y);
return make(normS(x+mod));
}
bool operator==(const ModInt& b) const { return v==b.v;}
bool operator!=(const ModInt& b) const { return v!=b.v;}
friend istream& operator>>(istream &o,ModInt& x){
ll tmp;
o>>tmp;
x=ModInt(tmp);
return o;
}
friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<998244353>;
typedef long long ll;
int N;
ll x[2000],y[2000];
ll gcd(ll x,ll y){
if(y==0) return abs(x);
return gcd(y,x%y);
}
using T = tuple<ll,ll,ll>;
map<T,int> cnt;
map<int,int> c2i;
mint p2[2001];
int main(){
cin>>N;
p2[0] = 1;
rep1(i,N) p2[i] = p2[i-1]*2;
for(int i=2;i<=N;i++){
int x = i*(i-1)/2;
c2i[x] = i;
}
rep(i,N) cin>>x[i]>>y[i];
rep(i,N) rep(j,i){
ll a = y[i]-y[j];
ll b = x[j]-x[i];
ll c = y[i]*x[j]-y[j]*x[i];
ll g = gcd(a,gcd(b,c));
if(a<0 || (a==0&&b<0)) g*=-1;
a/=g,b/=g,c/=g;
cnt[T(a,b,c)]++;
}
mint ans = p2[N];
for(auto it:cnt){
int n = c2i[it.sc];
ans -= p2[n]-n-1;
}
ans -= N+1;
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
E - ConvexScore |
User |
sigma425 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2723 Byte |
Status |
AC |
Exec Time |
11 ms |
Memory |
1792 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 |
5 ms |
896 KB |
1_006.txt |
AC |
1 ms |
256 KB |
1_007.txt |
AC |
5 ms |
768 KB |
1_008.txt |
AC |
4 ms |
640 KB |
1_009.txt |
AC |
4 ms |
768 KB |
1_010.txt |
AC |
2 ms |
512 KB |
1_011.txt |
AC |
5 ms |
1024 KB |
1_012.txt |
AC |
6 ms |
1152 KB |
1_013.txt |
AC |
4 ms |
768 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 |
11 ms |
1792 KB |
1_018.txt |
AC |
11 ms |
1792 KB |
1_019.txt |
AC |
7 ms |
1024 KB |
1_020.txt |
AC |
7 ms |
1024 KB |
1_021.txt |
AC |
7 ms |
1152 KB |
1_022.txt |
AC |
8 ms |
1408 KB |
1_023.txt |
AC |
9 ms |
1664 KB |
1_024.txt |
AC |
9 ms |
1664 KB |
1_025.txt |
AC |
9 ms |
1536 KB |
1_026.txt |
AC |
8 ms |
1536 KB |
1_027.txt |
AC |
2 ms |
256 KB |
1_028.txt |
AC |
2 ms |
256 KB |
1_029.txt |
AC |
9 ms |
1536 KB |
1_030.txt |
AC |
10 ms |
1792 KB |
1_031.txt |
AC |
10 ms |
1792 KB |
1_032.txt |
AC |
10 ms |
1792 KB |
1_033.txt |
AC |
10 ms |
1792 KB |
1_034.txt |
AC |
10 ms |
1792 KB |
1_035.txt |
AC |
7 ms |
1024 KB |