Submission #70587351

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using i64 = int64_t;
using i32 = int32_t;
void chmax(auto& a, auto b) { if (a < b) a = b; }
int sz(const auto& a) { return (int)size(a); }
#define rep(i, a, b) for (int i = a; i < (b); i++)

struct P {
    i32 x, y;
    friend auto operator<=>(P a, P b) { return tie(a.x, a.y) <=> tie(b.x, b.y); }
};
const P NIL = {INT_MIN, INT_MIN};
P operator+(P a, P b) { return {a.x + b.x, a.y + b.y}; }
P operator-(P a, P b) { return {a.x - b.x, a.y - b.y}; }
P operator-(P a) { return {-a.x, -a.y}; }
bool operator==(P a, P b) { return a.x == b.x && a.y == b.y; }
i64 dot(P a, P b) { return (i64)a.x * b.x + (i64)a.y * b.y; }
i64 cross(P a, P b) { return (i64)a.x * b.y - (i64)a.y * b.x; }
i64 cross(P a, P b, P c) { return cross(b - a, c - a); }
P rotate(P a) { return {-a.y, a.x}; }
using Poly = vector<P>;

Poly convex_hull(Poly A) {
    ranges::sort(A, less<>{});
    Poly lo, hi;
    for (P p : A) {
        while (lo.size() >= 2 && cross(lo.rbegin()[1], lo.back(), p) <= 0) lo.pop_back();
        while (hi.size() >= 2 && cross(hi.rbegin()[1], hi.back(), p) >= 0) hi.pop_back();
        lo.push_back(p);
        hi.push_back(p);
    }
    if (lo.size() == 1) return lo;
    lo.pop_back();
    lo.insert(lo.end(), hi.rbegin(), hi.rend() - 1);
    return lo;
}

struct T {
    array<P, 4> top4; // vec 方向の上位 4 点
    P nx_vec;         // 子孫のいずれかの top4 が更新されるタイミング
    P nx_vec_8;       // 子の top4 を合わせた 8 点の中の top4 が更新されるタイミング
};
T op(T& a, T& b, const P vec) {
    // dot(vec, *) で比較 (cross(vec, *) で tie-break)
    auto cmp = [&](P a, P b) {
        P v = b - a;
        return pair{dot(vec, v), cross(vec, v)} > pair<i64, i64>{};
    };
    // top4 を cmp でバブルソートしておく (ソート済みなら速い)
    // NIL なら末尾に持っていく
    auto sort_top4 = [&](array<P, 4>& top4) {
        int N = 4, i = 0;
        while (i < N) {
            if (top4[i] == NIL) {
                for (int j = i; j + 1 < N; j++) top4[j] = top4[j + 1];
                top4[N - 1] = NIL;
                N--;
            } else {
                for (int j = i; j--; ) {
                    if (cmp(top4[j], top4[j + 1])) {
                        swap(top4[j], top4[j + 1]);
                    } else break;
                }
                i++;
            }
        }
    };
    sort_top4(a.top4);
    sort_top4(b.top4);
    
    // この頂点が次に更新されるときの方向を求める
    auto upd = [&](P& nx_vec, P v) {
        if (cross(vec, v) <= 0) return;
        if (cross(v, nx_vec) > 0) nx_vec = v;
    };
    
    auto A = a.top4, B = b.top4;
    { // 上 4 点 = A と 下 4 点 = B に分ける
        int i = 0;
        for (; i < 4; i++) {
            P& b = B[i];
            if (b == NIL) break;
            P& a = A[3 - i];
            if (a == NIL || cmp(a, b)) {
                swap(a, b);
            } else break;
        }
    }
    P nx_vec_8 = -vec;
    { // nx_vec_8 := 上 4 点と下 4 点がはじめて逆転する方向 を求める
        rep(j, 0, 4) {
            if (A[j] == NIL) continue;
            rep(k, 0, 4) {
                if (B[k] == NIL) continue;
                upd(nx_vec_8, rotate(A[j] - B[k]));
            }
        }
    }
    P nx_vec = a.nx_vec;
    upd(nx_vec, b.nx_vec);
    upd(nx_vec, nx_vec_8);
    sort_top4(A); // 返り値もソートしておく
    
    return T{A, nx_vec, nx_vec_8};
}
struct SegTree {
    int N;
    P vec;
    vector<T> seg;
    SegTree(P vec, vector<T> A) : N(A.size()), vec(vec), seg(N * 2) {
        rep(i, 0, N) seg[i + N] = A[i];
        for (int i = N; --i; ) seg[i] = op(seg[i << 1], seg[i << 1 | 1], vec);
    }
    P nx_vec() const { return seg[1].nx_vec; }
    auto top4() const { return seg[1].top4; }
    bool rotate(auto F) {
        vec = nx_vec();
        auto dfs = [&](auto dfs, int i) -> bool {
            // nx_vec == vec であるノードをすべて更新
            // top4 が更新されたかどうかを返す
            P v = seg[i].nx_vec;
            if (cross(vec, v) != 0) return false;
            if (dot(vec, v) <= 0) return false;
            if (i >= N) {
                seg[i] = F(i - N);
                return true;
            }
            bool updated = dfs(dfs, i << 1);
            updated |= dfs(dfs, i << 1 | 1);
            // 子の top4 が更新されなかったら、nx_vec のみ更新
            if (!updated && cross(vec, seg[i].nx_vec_8) > 0) {
                auto& nx_vec = seg[i].nx_vec;
                nx_vec = seg[i].nx_vec_8;
                if (cross(seg[i << 1].nx_vec, nx_vec) > 0) nx_vec = seg[i << 1].nx_vec;
                if (cross(seg[i << 1 | 1].nx_vec, nx_vec) > 0) nx_vec = seg[i << 1 | 1].nx_vec;
                return false;
            }
            auto top4_old = seg[i].top4;
            seg[i] = op(seg[i << 1], seg[i << 1 | 1], vec);
            if (i == 1) {
                // i == 1 なら、集合の一致でチェック
                ranges::sort(top4_old, greater<>{});
                ranges::sort(seg[i].top4, greater<>{});
            }
            return top4_old != seg[i].top4;
        };
        return dfs(dfs, 1);
    }
};

void solve() {
    // 入力 + color_of 構築 (20 ms)
    int N;
    cin >> N;
    vector<pair<P, int>> points(N);
    // 座標 → 色の hash_map
    unordered_map color_of(initializer_list<pair<const P, int>>{}, N, [](P a) { return bit_cast<u64>(a); });
    for (auto& [p, c] : points) {
        cin >> p.x >> p.y >> c;
        color_of[p] = c;
    }
    
    // 色ごとに凸包を取る (20 ms)
    ranges::sort(points, {}, &pair<P, int>::second);
    vector<Poly> hulls;
    {
        auto L = points.begin();
        for (auto R = points.begin(); R++ != points.end(); ) {
            if (R != points.end() && R->second == prev(R)->second) continue;
            Poly A;
            A.reserve(R - L);
            for (auto it = L; it != R; it++) {
                A.push_back(it->first);
            }
            hulls.push_back(convex_hull(A));
            L = R;
        }
    }
    
    const int C = sz(hulls);
    if (C < 4) {
        cout << "0\n";
        return;
    }
    
    auto one = [&](const Poly& H, int i, P vec) {
        assert(0 <= i && i < sz(H));
        if (sz(H) == 1) {
            return T{{H[0], NIL, NIL, NIL}, -vec, -vec};
        }
        P u = H[i], v = H[i + 1 == sz(H) ? 0 : i + 1];
        return T{{u, NIL, NIL, NIL}, rotate(u - v), -vec};
    };
    
    // vec を y+ 側で 180 度回したときの top4 (As と Bs 合わせて 440 ms)
    vector<pair<P, array<P, 4>>> As;
    {
        // it[i] : hulls[i] 上の点のうち，dot(seg.vec, *) が最大のもの
        vector<int> it(C);
        rep(i, 0, C) {
            const Poly& H = hulls[i];
            it[i] = ranges::max_element(H, less<>{}) - H.begin();
        }
        const P vec = P{1, 0};
        SegTree seg(vec, [&] {
            vector<T> A(C);
            rep(i, 0, C) A[i] = one(hulls[i], it[i], vec);
            return A;
        }());
        As.emplace_back(seg.vec, seg.top4());
        while (1) {
            if (cross(vec, seg.nx_vec()) <= 0) break;
            if (!seg.rotate([&](int i) {
                const Poly& H = hulls[i];
                int& p = it[i];
                if (++p == sz(H)) p = 0;
                return one(H, p, seg.vec);
            })) continue;  // top4 が同じならスキップ
            As.emplace_back(seg.vec, seg.top4());
        }
    }
    
    // vec を y- 側で 180 度回したときの top4
    vector<pair<P, array<P, 4>>> Bs;
    {
        // it[i] : hulls[i] 上の点のうち，dot(vec, *) が最大のもの
        vector<int> it(C);
        rep(i, 0, C) {
            const Poly& H = hulls[i];
            it[i] = ranges::min_element(H, less<>{}) - H.begin();
        }
        const P vec = P{-1, 0};
        SegTree seg(vec, [&] {
            vector<T> A(C);
            rep(i, 0, C) A[i] = one(hulls[i], it[i], vec);
            return A;
        }());
        Bs.emplace_back(seg.vec, seg.top4());
        while (1) {
            if (cross(vec, seg.nx_vec()) <= 0) break;
            if (!seg.rotate([&](int i) {
                const Poly& H = hulls[i];
                int& p = it[i];
                if (++p == sz(H)) p = 0;
                return one(H, p, seg.vec);
            })) continue;  // top4 が同じならスキップ
            Bs.emplace_back(seg.vec, seg.top4());
        }
    }

    // sz(As) + sz(Bs) ≤ N くらいのはず
    As.push_back(Bs[0]);
    Bs.push_back(As[0]);

    vector<tuple<P, int, int>> cands_AC;
    { 
        // ベクトル AC を dedup するための hash_set
        unordered_set hash_AC(initializer_list<pair<P, P>>{}, N * 16, [](const pair<P, P>& p) {
            u64 h = bit_cast<u64>(p.first) * 0x9e3779b97f4a7c16 + bit_cast<u64>(p.second);
            h ^= h << 13;
            h ^= h >> 7;
            h ^= h << 17;
            return h;
        });
        // 目標方向 (= vec) を回転させながら、点 A, C を top4 から選び、ベクトル AC の候補を列挙 (170 ms)
        auto p = As.begin(), q = Bs.begin();
        while (p->first != P{-1, 0}) {
            for (P a : p->second) {
                for (P c : q->second) {
                    int c1 = color_of[a], c3 = color_of[c];
                    if (c1 == c3) continue;
                    if (c1 > c3) swap(c1, c3);
                    if (!hash_AC.insert(minmax({a, c})).second) continue;
                    P v = rotate(a - c); // 90 度回転させておき，B-D の目標ベクトルにする
                    assert(v != P{});
                    // y+ 方向に正規化
                    if (P{v.y, v.x} < P{}) v = -v; 
                    cands_AC.emplace_back(v, c1, c3);
                }
            }
            const i64 c = cross(next(p)->first, -next(q)->first);
            if (c >= 0) p++;
            if (c <= 0) q++;
        }
    }
    // sz(cands_AC) ≤ 4N くらいのはず

    { // sort cands_AC (10 ms)
        ranges::sort(cands_AC, [](const auto& a, const auto& b) {
            return cross(get<0>(a), get<0>(b)) > 0;
        });
    }

    i64 ans = 0;
    { // AC を回して、点 B, D を目標方向の top4 から選び、四角形を列挙 (80 ms)
        auto p = As.begin(), q = Bs.begin();
        for (auto [vec, c1, c3] : cands_AC) {
            while (cross(next(p)->first, vec) > 0) p++;
            while (cross(-next(q)->first, vec) > 0) q++;
            for (P b : p->second) {
                const int c2 = color_of[b];
                if (c2 == c1 || c2 == c3) continue;
                for (P d : q->second) {
                    const int c4 = color_of[d];
                    if (c4 == c1 || c4 == c2 || c4 == c3) continue;
                    chmax(ans, dot(vec, b - d));
                }
            }
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    rep(_, 0, T) solve();
}

Submission Info

Judge Result