結果
問題 | No.2173 Nightcord |
ユーザー | t33f |
提出日時 | 2022-12-25 12:17:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,185 bytes |
コンパイル時間 | 1,584 ms |
コンパイル使用メモリ | 95,336 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-18 23:56:31 |
合計ジャッジ時間 | 6,816 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 271 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 4 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | WA | - |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | WA | - |
testcase_12 | AC | 4 ms
5,248 KB |
testcase_13 | WA | - |
testcase_14 | AC | 17 ms
5,248 KB |
testcase_15 | AC | 13 ms
5,248 KB |
testcase_16 | AC | 5 ms
5,248 KB |
testcase_17 | WA | - |
testcase_18 | AC | 4 ms
5,248 KB |
testcase_19 | WA | - |
testcase_20 | AC | 4 ms
5,248 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 4 ms
5,248 KB |
testcase_24 | WA | - |
testcase_25 | AC | 4 ms
5,248 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 5 ms
5,248 KB |
testcase_29 | WA | - |
testcase_30 | AC | 5 ms
5,248 KB |
testcase_31 | WA | - |
testcase_32 | AC | 176 ms
5,248 KB |
testcase_33 | AC | 326 ms
5,248 KB |
testcase_34 | AC | 364 ms
5,248 KB |
testcase_35 | AC | 166 ms
5,248 KB |
testcase_36 | AC | 208 ms
5,248 KB |
testcase_37 | AC | 306 ms
5,248 KB |
testcase_38 | AC | 54 ms
5,248 KB |
testcase_39 | AC | 166 ms
5,248 KB |
testcase_40 | AC | 337 ms
5,248 KB |
testcase_41 | AC | 213 ms
5,248 KB |
testcase_42 | AC | 165 ms
5,248 KB |
testcase_43 | AC | 21 ms
5,248 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 62 ms
5,248 KB |
testcase_46 | AC | 100 ms
5,248 KB |
testcase_47 | AC | 83 ms
5,248 KB |
testcase_48 | AC | 42 ms
5,248 KB |
testcase_49 | AC | 4 ms
5,248 KB |
testcase_50 | AC | 16 ms
5,248 KB |
testcase_51 | AC | 91 ms
5,248 KB |
testcase_52 | AC | 3 ms
5,248 KB |
testcase_53 | AC | 98 ms
5,248 KB |
testcase_54 | AC | 144 ms
5,248 KB |
testcase_55 | AC | 30 ms
5,248 KB |
testcase_56 | AC | 60 ms
5,248 KB |
ソースコード
#include <numeric> #include <cassert> #include <algorithm> #include <vector> #include <iostream> using namespace std; using P = pair<int, int>; P operator-(const P lhs, const P rhs) { return {lhs.first - rhs.first, lhs.second - rhs.second}; } long long cp(P a, P b) { return (long long)a.first * b.second - (long long)a.second * b.first; } long long dotp(P a, P b) { return (long long)a.first * b.first + (long long)a.second * b.second; } vector<int> convex_hull(const vector<P> &p) { const size_t n = p.size(); vector<int> ps(n); iota(ps.begin(), ps.end(), 0); sort(ps.begin(), ps.end(), [&](int i, int j) { return p[i] < p[j]; }); vector<int> lower; for (int i : ps) { while (lower.size() > 1) { const size_t k = lower.size(); P cur = p[i], prev = p[lower[k-1]], pprev = p[lower[k-2]]; if (cp(prev - pprev, cur - pprev) > 0) break; else lower.pop_back(); } lower.push_back(i); } reverse(ps.begin(), ps.end()); vector<int> upper; for (int i : ps) { while (upper.size() > 1) { const size_t k = upper.size(); P cur = p[i], prev = p[upper[k-1]], pprev = p[upper[k-2]]; if (cp(prev - pprev, cur - pprev) > 0) break; else upper.pop_back(); } upper.push_back(i); } lower.insert(lower.end(), upper.begin()+1, upper.end()); return lower; } ostream &operator<<(ostream &out, P p) { out << p.first << ' ' << p.second; return out; } bool contained_in(P c, const vector<int> &ch, const vector<P> &vs) { assert(ch.size() <= vs.size() + 1); bool pos = false; for (int i = 0; i + 1 < ch.size(); ++i) { const P p = vs[ch[i]], q = vs[ch[i + 1]]; const long long x = cp(p - c, q - c); if (x < 0) return false; if (x > 0) pos = true; else if (x == 0 && dotp(p - c, q - c) < 0) return true; } return pos; } bool check1(const vector<int> &ch, const vector<P> &vs, const vector<P> &ps) { for (const auto &c : ps) if (contained_in(c, ch, vs)) return true; return false; } bool segments_intersect(P p1, P q1, P p2, P q2) { const auto [x1, y1] = p1; const auto [z1, w1] = q1; const auto [x2, y2] = p2; const auto [z2, w2] = q2; if (max(x1, z1) < min(x2, z2) || max(x2, z2) < min(x1, z1) || max(y1, w1) < min(y2, w2) || max(y2, w2) < min(y1, w1)) return false; const int a1 = w1 - y1, b1 = x1 - z1, c1 = -x1 * w1 + y1 * z1, a2 = w2 - y2, b2 = x2 - z2, c2 = -x2 * w2 + y2 * z2, vp1 = a2 * x1 + b2 * y1 + c2, vq1 = a2 * z1 + b2 * w1 + c2, vp2 = a1 * x2 + b1 * y2 + c1, vq2 = a1 * z2 + b1 * w2 + c1; // cerr << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n'; // cerr << vp1 << ' ' << vq1 << ' ' << vp2 << ' ' << vq2 << endl; if ((vp1 > 0 && vq1 > 0) || (vp1 < 0 && vq1 < 0)) return false; else return !((vp2 > 0 && vq2 > 0) || (vp2 < 0 && vq2 < 0)); } bool check2(const vector<int> &ch1, const vector<P> &vs1, const vector<int> &ch2, const vector<P> &vs2) { for (int i = 0; i + 1 < ch1.size(); ++i) { const P p1 = vs1[ch1[i]], q1 = vs1[ch1[i + 1]]; for (int j = 0; j + 1 < ch2.size(); ++j) { const P p2 = vs2[ch2[j]], q2 = vs2[ch2[j + 1]]; if (segments_intersect(p1, q1, p2, q2)) return true; } } return false; } bool check3(const vector<P> &ps1, const vector<P> &ps2) { if (ps2.size() <= 1) return false; auto compare_arg = [](P lhs, P rhs) { const auto [x1, y1] = lhs; const auto [x2, y2] = rhs; const bool u1 = y1 > 0 || (y1 == 0 && x1 >= 0), u2 = y2 > 0 || (y2 == 0 && x2 >= 0); if (u1 != u2) return u1; else return cp(lhs, rhs) > 0; }; for (const P ¢er : ps1) { vector<P> ps; for (int j = 0; j < ps2.size(); ++j) ps.emplace_back(ps2[j] - center); sort(ps.begin(), ps.end(), compare_arg); // cerr << "center = " << center << endl; // for (P p : ps) cerr << p << ", "; cerr << endl; int j = 0, m = 1; while (j < ps.size()) { // cerr << j << endl; while (j != m && cp(ps[j], ps[m]) > 0) if (++m == ps.size()) m = 0; if (cp(ps[j], ps[m]) == 0 && dotp(ps[j], ps[m]) < 0) { // cerr << center << ' ' << ps[j] << ' ' << ps[m] << endl; return true; } ++j; } } return false; } int main() { int n, k; cin >> n >> k; vector<int> x(n), y(n), c(n); for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> c[i]; vector<P> rp, bp; for (int i = 0; i < n; ++i) if (c[i] == 1) rp.emplace_back(x[i], y[i]); else bp.emplace_back(x[i], y[i]); if (rp.empty() || bp.empty()) { cout << "No\n"; cerr << "empty\n"; return 0; } const vector<int> rch = convex_hull(rp), bch = convex_hull(bp); if (k > 3) cout << (check1(rch, rp, bp) || check1(bch, bp, rp) || check2(bch, bp, rch, rp) ? "Yes\n": "No\n"); else cout << (check3(rp, bp) || check3(bp, rp) ? "Yes\n": "No\n"); }