Submission #2252122
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// EPS
constexpr double EPS = 1e-9;
/// --- Geometory Library {{{ ///
using Point = complex<int>;
#define X real()
#define Y imag()
#define dot(a, b) real(conj(a)*b)
#define cross(a, b) imag(conj(a)*b)
#define norm abs
// +1 : ccw
// -1 : cw
// +2 : a--b--c
// -2 : b--c--a
// 0 : b--a--c
// int ccw(Point a, Point b, Point c) {
// b -= a; c -= a;
// if(cross(b, c) > EPS) return +1;
// if(cross(b, c) < -EPS) return -1;
// if(dot(b, c) < 0) return 0;
// if(norm(b) < norm(c)) return +2;
// return -2;
// }
//
// double arg(Point a, Point b) {
// return acos(dot(a, b) / norm(a) / norm(b));
// }
/// ---}}} ///
bool para(Point a, Point b, Point c) {
b -= a; c -= a;
return b.X * c.Y == b.Y * c.X;
}
constexpr ll mod = 998244353;
/// --- modulo Library {{{ ///
constexpr ll extgcd(ll a, ll b, ll& x, ll& y) {
if(b==0) {
x = 1; y = 0;
return a;
}
ll d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
constexpr ll modpow(ll a, ll b, ll mod = 1e9 + 7) {
a = (a % mod + mod) % mod;
ll r = 1;
while(b){
if(b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
constexpr ll modinv(ll a, ll mod = 1e9 + 7) {
a = (a % mod + mod) % mod;
ll x = 0, y = 0;
extgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}
template<int N, int mod = 1e9 + 7> struct Factorial {
int arr[N+1], inv[N+1];
int operator[](int i) const { return arr[i]; }
constexpr Factorial(): arr(), inv() {
arr[0] = 1;
for(int i = 1; i <= N; i++) {
arr[i] = (ll) i * arr[i - 1] % mod;
}
inv[N] = modinv(arr[N], mod);
for(int i = N-1; i >= 0; i--) {
inv[i] = (ll) (i + 1) * inv[i + 1] % mod;
}
}
int C(int n, int r) const {
if(n < 0 || r < 0 || n < r) return 0;
return (ll) arr[n] * inv[r] % mod * inv[n - r] % mod;
}
};
/// }}}--- ///
constexpr Factorial<200, mod> fact;
bool done[200][200];
// 点集合のうち,(同一直線上の点のみを選ぶ)を覗いた集合の数とスコアが一致
// O(N^3)
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
vector<Point> p(n);
for(int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
p[i] = Point(x, y);
}
ll ans = modpow(2, n, mod) - fact.C(n, 2) - n - 1;
ans %= mod;
for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {
if(done[i][j]) continue;
int cnt = 2;
vector<int> vs;
vs.emplace_back(i);
vs.emplace_back(j);
for(int k = j + 1; k < n; k++) {
if(para(p[i], p[j], p[k])) cnt++, vs.emplace_back(k);
}
for(int s = 0; s < (int) vs.size(); s++) for(int t = s + 1; t < (int) vs.size(); t++) {
done[vs[s]][vs[t]] = 1;
}
ans -= modpow(2, cnt, mod) - fact.C(cnt, 2) - cnt - 1;
ans %= mod;
}
cout << (ans + mod) % mod << endl;
}
Submission Info
Submission Time |
|
Task |
E - ConvexScore |
User |
luma |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2976 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
256 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 |
3 ms |
256 KB |
1_006.txt |
AC |
1 ms |
256 KB |
1_007.txt |
AC |
3 ms |
256 KB |
1_008.txt |
AC |
2 ms |
256 KB |
1_009.txt |
AC |
3 ms |
256 KB |
1_010.txt |
AC |
2 ms |
256 KB |
1_011.txt |
AC |
3 ms |
256 KB |
1_012.txt |
AC |
4 ms |
256 KB |
1_013.txt |
AC |
3 ms |
256 KB |
1_014.txt |
AC |
1 ms |
256 KB |
1_015.txt |
AC |
1 ms |
256 KB |
1_016.txt |
AC |
1 ms |
256 KB |
1_017.txt |
AC |
6 ms |
256 KB |
1_018.txt |
AC |
7 ms |
256 KB |
1_019.txt |
AC |
4 ms |
256 KB |
1_020.txt |
AC |
4 ms |
256 KB |
1_021.txt |
AC |
5 ms |
256 KB |
1_022.txt |
AC |
5 ms |
256 KB |
1_023.txt |
AC |
6 ms |
256 KB |
1_024.txt |
AC |
6 ms |
256 KB |
1_025.txt |
AC |
6 ms |
256 KB |
1_026.txt |
AC |
5 ms |
256 KB |
1_027.txt |
AC |
1 ms |
256 KB |
1_028.txt |
AC |
1 ms |
256 KB |
1_029.txt |
AC |
5 ms |
256 KB |
1_030.txt |
AC |
6 ms |
256 KB |
1_031.txt |
AC |
6 ms |
256 KB |
1_032.txt |
AC |
6 ms |
256 KB |
1_033.txt |
AC |
6 ms |
256 KB |
1_034.txt |
AC |
6 ms |
256 KB |
1_035.txt |
AC |
4 ms |
256 KB |