Untitled

 avatar
unknown
c_cpp
a year ago
5.4 kB
5
Indexable
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;
using db = long double;

constexpr db EPS = 1e-10;

template <typename T>
struct point {
    T x, y;

    point() {
        x = 0;
        y = 0;
    }

    point(const T &_x, const T &_y) {
        x = _x;
        y = _y;
    }

    point(const point &a, const point &b) {
        x = b.x - a.x;
        y = b.y - a.y;
    }

    point operator+(const point &other) {
        return point(x + other.x, y + other.y);
    }

    point operator-(const point &other) {
        return point(x - other.x, y - other.y);
    }

    T operator*(const point &other) {
        return x * other.x + y * other.y;
    }

    T operator%(const point &other) {
        return x * other.y - other.x * y;
    }

    bool operator<(const point &other) {
        return make_pair(x, y) < make_pair(other.x, other.y);
    }
};

template <typename T>
istream& operator>>(istream& in, point<T> &p) {
    in >> p.x >> p.y;
    return in;
}

template <typename T>
ostream& operator<<(ostream& out, point<T> &p) {
    out << p.x << ' ' << p.y;
    return out;
}

template <typename T>
T len2(const point<T> &p) {
    return p.x * p.x + p.y * p.y;
}

template <typename T>
T dist2(const point<T> &a, const point<T> &b) {
    return len2(point<T>(a, b));
}

using pt = point<ll>;

db PolarAngle(pt p) {
    return atan2(p.y, p.x);
}

void test_case() {
    int n, t;
    cin >> n >> t;
    vector<pt> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i];
    }
    vector<int> go(n * n, -1);
    vector<vector<int>> gr(n * n);
    for (int j = 0; j < n; j++) {
        vector<int> order;
        for (int i = 0; i < n; i++) {
            if (i == j) continue;
            order.push_back(i);
        }
        sort(order.begin(), order.end(), [&](int lhs, int rhs) {
            pt a = pts[lhs] - pts[j];
            pt b = pts[rhs] - pts[j];
            db pa = PolarAngle(a), pb = PolarAngle(b);
            return pa < pb - EPS || (abs(pa - pb) <= EPS && len2(a) < len2(b));
        });
        for (int i = 0; i < n; i++) {
            if (i == j) continue;
            int first;
            db pa = PolarAngle(pt(pts[i], pts[j]));
            {
                if (PolarAngle(pts[order.back()] - pts[j]) < pa) {
                    first = 0;
                } else {
                    int L = -1, R = n - 2;
                    while (L + 1 != R) {
                        int M = (L + R) / 2;
                        pt pm = pts[order[M]] - pts[j];
                        if (PolarAngle(pm) < pa) {
                            L = M;
                        } else {
                            R = M;
                        }
                    }
                    first = R;
                }
            }
            go[i + j * n] = j + order[(first + t - 1) % (n - 1)] * n;
            gr[j + order[(first + t - 1) % (n - 1)] * n].push_back(i + j * n);
        }
    }
    vector<char> used1(n * n, 0);
    vector<bool> in_cycle(n * n, false);
    vector<int> color(n, 3);
    auto dfs1 = [&](auto self, int v) -> int {
        used1[v] = 1;
        int g = go[v];
        if (used1[g] == 0) {
            int r = self(self, g);
            if (r != -1) {
                in_cycle[v] = true;
                color[v % n] = 1;
            }
            used1[v] = 2;
            return (r == v ? -1 : r);
        } else if (used1[g] == 1) {
            in_cycle[v] = true;
            color[v % n] = 1;
            used1[v] = 2;
            return g;
        } else {
            used1[v] = 2;
            return -1;
        }
    };
    for (int i = 0; i < n * n; i++) {
        if (!used1[i] && go[i] != -1) {
            dfs1(dfs1, i);
        }
    }
    vector<int> tin(n * n), tout(n * n);
    int ti = 1;
    auto dfs2 = [&](auto self, int v) -> void {
        tin[v] = ti++;
        for (int &g : gr[v]) {
            assert(!in_cycle[g]);
            if (!tin[g]) {
                self(self, g);
            }
        }
        tout[v] = ti++;
    };
    for (int i = 0; i < n * n; i++) {
        if (go[i] != -1 && !tin[i] && in_cycle[go[i]] && !in_cycle[i]) {
            dfs2(dfs2, i);
        }
    }
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) continue;
        vector<pair<int, int>> v;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            v.emplace_back(tin[i + j * n], tout[i + j * n]);
        }
        sort(v.rbegin(), v.rend());
        set<int> s;
        for (auto &[in, out] : v) {
            if (s.lower_bound(out) != s.begin()) {
                color[i] = 2;
                break;
            }
            s.insert(out);
        }
    }
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            cout << 'G';
        } else if (color[i] == 2) {
            cout << 'B';
        } else if (color[i] == 3) {
            cout << 'R';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}
Editor is loading...
Leave a Comment