結果
問題 | No.1497 Triangle |
ユーザー |
![]() |
提出日時 | 2021-05-03 16:07:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 261 ms / 2,000 ms |
コード長 | 2,577 bytes |
コンパイル時間 | 2,445 ms |
コンパイル使用メモリ | 212,456 KB |
最終ジャッジ日時 | 2025-01-21 06:15:07 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h>using namespace std;using P = pair<int, int>;const double EPS = 1e-10;P operator-(const P& a, const P& b){ return {a.first - b.first, a.second - b.second}; }int cross(const P& a, const P& b){ return a.first * b.second - a.second * b.first; }int dot(const P& a, const P& b){ return a.first * b.first + a.second * b.second; }double atan(const P& a){ return atan2(a.second, a.first); }struct Line{double mn = INFINITY, mx = -INFINITY;};int main(){int N;cin >> N;vector<P> A(N);for(auto& [x, y] : A) cin >> x >> y;auto cross = [&](int i, int j, int k){return ::cross(A[j] - A[i], A[k] - A[i]);};auto dot = [&](int i, int j, int k){return ::dot(A[j] - A[i], A[k] - A[i]);};auto normal = [&](int i, int j){return ::atan(A[j] - A[i]);};auto check = [](Line a, Line b, Line c) -> bool {if(a.mn > b.mn) swap(a, b);if(b.mn > c.mn) swap(b, c);if(a.mn > b.mn) swap(a, b);assert(c.mn - a.mn < M_PI * 2);if(max({a.mx, b.mx, c.mx}) - a.mn <= M_PI) return 0;a.mn += M_PI * 2; a.mx += M_PI * 2;if(max({a.mx, b.mx, c.mx}) - b.mn <= M_PI) return 0;b.mn += M_PI * 2; b.mx += M_PI * 2;if(max({a.mx, b.mx, c.mx}) - c.mn <= M_PI) return 0;return 1;};map<int, Line> line_;for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(i != j){int bit1 = 0, bit2 = 0;for(int k = 0; k < N; k++){const int c = cross(i, j, k);if(c > 0){bit1 ^= 1 << k;bit2 ^= 1 << k;}if(c == 0) (dot(i, j, k) > 0 ? bit1 : bit2) ^= 1 << k;}line_[bit1].mx = normal(i, j) - EPS;line_[bit2].mn = normal(i, j) + EPS;}vector line(line_.begin(), line_.end());for(auto& [bit, l] : line){auto& [mn, mx] = l;assert(mn != INFINITY && mx != -INFINITY);if(mn > mx) mx += M_PI * 2;assert(mn < mx);assert(mx - mn < M_PI * 2);}unordered_set<int> ans;ans.insert(0);ans.insert((1 << N) - 1);for(auto& [bit1, l] : line) for(auto& [bit2, l] : line){if(bit1 < bit2) break;ans.insert(bit1 & bit2);}for(auto& [bit1, l1] : line) for(auto& [bit2, l2] : line){if(bit1 == bit2) break;for(auto& [bit3, l3] : line){if(bit2 == bit3) break;if(check(l1, l2, l3)) ans.insert(bit1 & bit2 & bit3);}}cout << ans.size() << endl;}