Submission #1606288
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define mp make_pair #define pb push_back #define ll long long #define maxN 211 #define mod 998244353 int n, i, j, k; pair<int, int> P[maxN]; vector< pair<int, int> > ord; ll pows[maxN]; ll ans, dx, dy, d; ll gcd(ll a, ll b) { if (a < 0) a *= -1; if (b < 0) b *= -1; if (a < b) swap(a, b); while (b > 0) { a %= b; swap(a, b); } return a; } int main() { // freopen("test.in","r",stdin); cin >> n; for (i = 1; i <= n; i++) cin >> P[i].first >> P[i].second; pows[0] = 1; for (i = 1; i <= n; i++) pows[i] = (pows[i - 1] * 2) % mod; ans = pows[n]; for (i = 1; i <= n; i++) { ord.clear(); for (j = i + 1; j <= n; j++) { dx = P[i].first - P[j].first; dy = P[i].second - P[j].second; if (dx < 0) { dx *= -1; dy *= -1; } if (dx == 0 && dy < 0) dy *= -1; d = gcd(dx, dy); dx /= d; dy /= d; ord.pb(mp(dx, dy)); } sort(ord.begin(), ord.end()); for (j = 0; j < ord.size(); j = k) { for (k = j; k < ord.size(); k++) if (ord[j] != ord[k]) break; ans += mod - pows[k - j] + 1; ans %= mod; } ans += mod - 1; ans %= mod; } ans += mod - 1; ans %= mod; cout << ans; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - ConvexScore |
User | atatomir |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1700 Byte |
Status | AC |
Exec Time | 5 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 | 2 ms | 256 KB |
1_010.txt | AC | 2 ms | 256 KB |
1_011.txt | AC | 2 ms | 256 KB |
1_012.txt | AC | 2 ms | 256 KB |
1_013.txt | AC | 2 ms | 256 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 | 5 ms | 256 KB |
1_018.txt | AC | 5 ms | 256 KB |
1_019.txt | AC | 3 ms | 256 KB |
1_020.txt | AC | 3 ms | 256 KB |
1_021.txt | AC | 4 ms | 256 KB |
1_022.txt | AC | 4 ms | 256 KB |
1_023.txt | AC | 3 ms | 256 KB |
1_024.txt | AC | 3 ms | 256 KB |
1_025.txt | AC | 3 ms | 256 KB |
1_026.txt | AC | 3 ms | 256 KB |
1_027.txt | AC | 2 ms | 256 KB |
1_028.txt | AC | 2 ms | 256 KB |
1_029.txt | AC | 4 ms | 256 KB |
1_030.txt | AC | 5 ms | 256 KB |
1_031.txt | AC | 5 ms | 256 KB |
1_032.txt | AC | 5 ms | 256 KB |
1_033.txt | AC | 5 ms | 256 KB |
1_034.txt | AC | 4 ms | 256 KB |
1_035.txt | AC | 3 ms | 256 KB |