Submission #2236563
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FF first
#define SS second
#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
for(auto& x: xs)
is >> x;
return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
for(unsigned int i=0;i<xs.size();++i)
os << (i?" ":"") << xs[i];
return os;
}
template<class T>
void maxi(T& x, T y){
if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 998244353;
LL powm(LL x, LL y){
if(y <= 0) return 1ll;
return powm(x*x%MOD, y/2) * (y%2?x:1ll) % MOD;
}
bool ison(PLL p1, PLL p2, PLL q){
p1.FF -= q.FF;
p1.SS -= q.SS;
p2.FF -= q.FF;
p2.SS -= q.SS;
return p1.FF * p2.SS - p1.SS * p2.FF == 0;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
LL N;
cin >> N;
vector<PLL> xs(N);
cin >> xs;
LL ans = (powm(2, N) + MOD - N - 1) % MOD;
set<PLL> memo;
REP(i,N) REP(j,i){
VI ps;
REP(k,N){
if(ison(xs[i], xs[j], xs[k])){
ps.PB(k);
}
}
SORT(ps);
auto p = MP(ps[0], ps[1]);
if(memo.count(p)) continue;
memo.insert(p);
ans = (ans + MOD - (powm(2, SZ(ps)) - SZ(ps) - 1)) % MOD;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - ConvexScore |
User |
okaduki |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2201 Byte |
Status |
AC |
Exec Time |
56 ms |
Memory |
1536 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 |
6 ms |
768 KB |
1_006.txt |
AC |
1 ms |
256 KB |
1_007.txt |
AC |
11 ms |
640 KB |
1_008.txt |
AC |
7 ms |
512 KB |
1_009.txt |
AC |
9 ms |
640 KB |
1_010.txt |
AC |
3 ms |
384 KB |
1_011.txt |
AC |
9 ms |
896 KB |
1_012.txt |
AC |
11 ms |
1024 KB |
1_013.txt |
AC |
7 ms |
640 KB |
1_014.txt |
AC |
1 ms |
256 KB |
1_015.txt |
AC |
33 ms |
256 KB |
1_016.txt |
AC |
9 ms |
256 KB |
1_017.txt |
AC |
19 ms |
1536 KB |
1_018.txt |
AC |
18 ms |
1536 KB |
1_019.txt |
AC |
18 ms |
896 KB |
1_020.txt |
AC |
19 ms |
896 KB |
1_021.txt |
AC |
19 ms |
1024 KB |
1_022.txt |
AC |
18 ms |
1152 KB |
1_023.txt |
AC |
19 ms |
1408 KB |
1_024.txt |
AC |
19 ms |
1408 KB |
1_025.txt |
AC |
20 ms |
1280 KB |
1_026.txt |
AC |
21 ms |
1280 KB |
1_027.txt |
AC |
56 ms |
256 KB |
1_028.txt |
AC |
56 ms |
256 KB |
1_029.txt |
AC |
20 ms |
1280 KB |
1_030.txt |
AC |
19 ms |
1536 KB |
1_031.txt |
AC |
19 ms |
1408 KB |
1_032.txt |
AC |
19 ms |
1408 KB |
1_033.txt |
AC |
19 ms |
1536 KB |
1_034.txt |
AC |
18 ms |
1536 KB |
1_035.txt |
AC |
22 ms |
896 KB |