TIOJ 1631：[IOI 2006] 點連接遊戲

TIOJ 1631：[IOI 2006] 點連接遊戲

題目大意：有一個平面跟 $n_0$ 個綠點、$n_1$ 個紅點，$s$ 為座標最大值，保證 $(0, s), (s, s)$ 是綠點，$(0, 0), (s, 0)$ 是紅點，三點不共線，想要綠點們互相連接，紅點們互相連接，形成兩棵不相交的樹。

解法：考慮現在有兩個綠點、一個紅點圍起來的三角形，如果中間的區域沒有點，那就終止，如果中間的點都是同一個顏色，那就挑同顏色的點連邊，否則我們可以隨機挑一個紅點，連一條邊，然後就會變成三個小三角形，就可以繼續遞迴了。時間複雜度 $O(n\times\log(n))$。

$\text{Code：}$

#include <bits/stdc++.h>
#include "lib1631.h"
using namespace std;

using ll = long long;

struct T {
    int c, x, y, id;
    T() {}
    T (int x, int y) : x (x), y (y) {}
    T (int c, int x, int y, int id) : c (c), x (x), y (y), id (id) {}
    T operator - (const T &v) const {
        return T (x - v.x, y - v.y);
    }
    ll operator * (const T &v) const {
        return 1ll * x * v.y - 1ll * y * v.x;
    }
};

int n[2], s;

mt19937 seed (time (NULL));
inline int rnd (int l, int r) {
    return uniform_int_distribution<int> (l, r) (seed);
}

inline bool inside (T p, T a, T b, T c) {
    int cnt = 0;
    cnt += (a - p) * (b - p) > 0;
    cnt += (b - p) * (c - p) > 0;
    cnt += (c - p) * (a - p) > 0;
    return cnt == 0 || cnt == 3;
}

void divide (T p, T a, T b, vector<T> v) {
    if (v.size() == 0) return;
    int cnt[2] = {};
    for (auto &[c, x, y, id] : v) cnt[c]++;
    if (cnt[0] == 0 || cnt[1] == 0) {
        for (T &vp : v) Report (vp.c, vp.id, p.c == vp.c ? p.id : a.id);
        return;
    }
    vector<T> vc, vpa, vpb, vab;
    for (T &vp : v) if (vp.c == p.c) vc.emplace_back (vp);
    T np = vc[rnd (0, vc.size() - 1)];
    Report (p.c, p.id, np.id);
    for (T &vp : v) if (vp.c != np.c || vp.id != np.id) {
        if (inside (vp, p, a, np)) vpa.emplace_back (vp);
        else if (inside (vp, p, b, np)) vpb.emplace_back (vp);
        else vab.emplace_back (vp);
    }
    divide (a, p, np, vpa);
    divide (b, p, np, vpb);
    divide (np, a, b, vab);
}

int main() {
    Init (n[0], n[1]);
    vector<T> v, vl, vr;
    for (int c = 0; c <= 1; c++) for (int i = 1; i <= n[c]; i++) {
        int x, y;
        Get (c, x, y);
        v.emplace_back (c, x, y, i);
        s = max ({s, x, y});
    }
    T p[4];
    int pos = 0;
    for (auto &[c, x, y, id] : v) {
        if ((x == 0 || x == s) && (y == 0 || y == s)) {
            p[pos++] = T (c, x, y, id);
        } else {
            if (inside (T (x, y), T (0, 0), T (0, s), T (s, s))) vl.emplace_back (c, x, y, id);
            else vr.emplace_back (c, x, y, id);
        }
    }
    Report (0, p[0].id, p[1].id);
    divide (p[2], p[0], p[1], vl);
    Report (1, p[2].id, p[3].id);
    divide (p[1], p[2], p[3], vr);
    Finish();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！