結果
問題 |
No.947 ABC包囲網
|
ユーザー |
![]() |
提出日時 | 2019-12-10 00:28:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 2,312 bytes |
コンパイル時間 | 2,056 ms |
コンパイル使用メモリ | 183,888 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-23 10:07:55 |
合計ジャッジ時間 | 3,632 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(bool b) { return b ? "true" : "false"; } template <size_t N> string to_string(bitset<N> bs) { string res; for (size_t i = 0; i < N; ++i) res += '0' + bs[i]; return res; } string to_string(vector<bool> v) { string res = "{"; for (bool e : v) res += to_string(e) + ", "; return res += "}"; } template <class T, class U> string to_string(pair<T, U> p); template <class C> string to_string(C c) { string res = "{"; for (auto e : c) res += to_string(e) + ", "; return res += "}"; } template <class T, class U> string to_string(pair<T, U> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } void debug() { cerr << '\n'; } template <class Head, class... Tail> void debug(Head head, Tail... tail) { cerr << ' ' << to_string(head), debug(tail...); } #ifdef LOCAL #define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__) #else #define DEBUG(...) #endif constexpr long double pi = acos(-1.0L); constexpr long double eps = 1e-15; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<long double> a; while (n--) { int x, y; cin >> x >> y; if (x == 0 and y == 0) { continue; } a.push_back(atan2((long double)y, x)); } n = a.size(); sort(begin(a), end(a)); for (int i = 0; i < n; ++i) { a.push_back(a[i] + 2 * pi); } DEBUG(a); long long res = (long long)n * (n - 1) * (n - 2) / 6; for (int i = 0; i < n; ++i) { int x = lower_bound(begin(a) + i, end(a), a[i] + pi + eps) - (begin(a) + i); DEBUG(i, x); res -= (x - 1) * (x - 2) / 2; } auto cmp = [](long double l, long double r) { return l + eps < r; }; auto tmod = [](long double x, long double mod) { x = fmod(x, mod); return x < 0 ? x + mod : x; }; map<long double, int, decltype(cmp)> mp(cmp); for (int i = 0; i < n; ++i) { ++mp[a[i]]; } DEBUG(res); for (auto e : mp) { long long x = e.second; DEBUG(e.first, x); long long y = mp.count(e.first + pi) ? mp[e.first + pi] : 0; long long z = x + y; res += z * (z - 1) * (z - 2) / 6; res -= x * (x - 1) * (x - 2) / 6; res -= y * (y - 1) * (y - 2) / 6; } cout << res << '\n'; }