#828369 (C++17) No.2173 Nightcord

• 問題: No.2173 Nightcord
• ユーザー: t33f
• 提出日時: 2022-12-25 12:21:00
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 369 ms / 2,525 ms
• コード長: 5,235 bytes
• コンパイル時間: 1,605 ms
• コンパイル使用メモリ: 94,992 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-17 14:32:46
• 合計ジャッジ時間: 6,351 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	283 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	AC	4 ms; 5,248 KB
testcase_10	AC	4 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	4 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	19 ms; 5,248 KB
testcase_15	AC	11 ms; 5,248 KB
testcase_16	AC	5 ms; 5,248 KB
testcase_17	AC	3 ms; 5,248 KB
testcase_18	AC	4 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	4 ms; 5,248 KB
testcase_21	AC	4 ms; 5,248 KB
testcase_22	AC	4 ms; 5,248 KB
testcase_23	AC	4 ms; 5,248 KB
testcase_24	AC	5 ms; 5,248 KB
testcase_25	AC	4 ms; 5,248 KB
testcase_26	AC	5 ms; 5,248 KB
testcase_27	AC	2 ms; 5,248 KB
testcase_28	AC	5 ms; 5,248 KB
testcase_29	AC	3 ms; 5,248 KB
testcase_30	AC	5 ms; 5,248 KB
testcase_31	AC	3 ms; 5,248 KB
testcase_32	AC	185 ms; 5,248 KB
testcase_33	AC	334 ms; 5,248 KB
testcase_34	AC	369 ms; 5,248 KB
testcase_35	AC	167 ms; 5,248 KB
testcase_36	AC	210 ms; 5,248 KB
testcase_37	AC	315 ms; 5,248 KB
testcase_38	AC	54 ms; 5,248 KB
testcase_39	AC	174 ms; 5,248 KB
testcase_40	AC	344 ms; 5,248 KB
testcase_41	AC	216 ms; 5,248 KB
testcase_42	AC	176 ms; 5,248 KB
testcase_43	AC	20 ms; 5,248 KB
testcase_44	AC	2 ms; 5,248 KB
testcase_45	AC	59 ms; 5,248 KB
testcase_46	AC	101 ms; 5,248 KB
testcase_47	AC	86 ms; 5,248 KB
testcase_48	AC	43 ms; 5,248 KB
testcase_49	AC	4 ms; 5,248 KB
testcase_50	AC	18 ms; 5,248 KB
testcase_51	AC	97 ms; 5,248 KB
testcase_52	AC	3 ms; 5,248 KB
testcase_53	AC	101 ms; 5,248 KB
testcase_54	AC	148 ms; 5,248 KB
testcase_55	AC	32 ms; 5,248 KB
testcase_56	AC	67 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 long long a1 = w1 - y1, b1 = x1 - z1, c1 = -(long long)x1 * w1 + (long long)y1 * z1,
        a2 = w2 - y2, b2 = x2 - z2, c2 = -(long long)x2 * w2 + (long long)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 &center : 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");
}