Untitled
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