Submit Info #42618

Problem Lang User Status Time Memory
Convex Layers cpp wleungBVG AC 607 ms 64.97 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.66 MiB
example_01 AC 2 ms 0.67 MiB
example_02 AC 0 ms 0.62 MiB
example_03 AC 0 ms 0.62 MiB
example_04 AC 1 ms 0.68 MiB
example_05 AC 0 ms 0.67 MiB
line_00 AC 158 ms 39.12 MiB
line_01 AC 191 ms 57.08 MiB
line_02 AC 69 ms 17.84 MiB
line_03 AC 204 ms 60.27 MiB
line_04 AC 18 ms 5.29 MiB
max_l_00 AC 235 ms 64.87 MiB
max_random_00 AC 607 ms 62.92 MiB
max_random_01 AC 597 ms 62.99 MiB
max_random_02 AC 593 ms 62.92 MiB
max_random_03 AC 591 ms 62.92 MiB
max_random_04 AC 596 ms 62.89 MiB
max_square_grid_00 AC 317 ms 62.89 MiB
max_t_00 AC 252 ms 64.97 MiB
max_x_00 AC 243 ms 62.92 MiB
max_y_00 AC 267 ms 62.96 MiB

#include <bits/stdc++.h> using namespace std; template <class C> constexpr int sz(const C &c) { return int(c.size()); } constexpr const char nl = '\n', sp = ' '; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; #if __SIZEOF_INT128__ using i128 = __int128_t; using ui128 = __uint128_t; #endif using T = long double; constexpr const T EPS = 1e-9; bool lt(T a, T b) { return a + EPS < b; } bool le(T a, T b) { return !lt(b, a); } bool gt(T a, T b) { return lt(b, a); } bool ge(T a, T b) { return !lt(a, b); } bool eq(T a, T b) { return !lt(a, b) && !lt(b, a); } bool ne(T a, T b) { return lt(a, b) || lt(b, a); } int sgn(T a) { return lt(a, 0) ? -1 : lt(0, a) ? 1 : 0; } struct eps_lt { bool operator () (T a, T b) const { return lt(a, b); } }; struct eps_le { bool operator () (T a, T b) const { return !lt(b, a); } }; struct eps_gt { bool operator () (T a, T b) const { return lt(b, a); } }; struct eps_ge { bool operator () (T a, T b) const { return !lt(a, b); } }; struct eps_eq { bool operator () (T a, T b) const { return !lt(a, b) && !lt(b, a); } }; struct eps_ne { bool operator () (T a, T b) const { return lt(a, b) || lt(b, a); } }; #define ref const pt & #define OP(op, U, a, x, y) pt operator op (U a) const { return pt(x, y); } \ pt &operator op##= (U a) { return *this = *this op a; } #define CMP(op, body) bool operator op (ref p) const { return body; } struct pt { T x, y; constexpr pt(T x = 0, T y = 0) : x(x), y(y) {} pt operator + () const { return *this; } pt operator - () const { return pt(-x, -y); } OP(+, ref, p, x + p.x, y + p.y) OP(-, ref, p, x - p.x, y - p.y) OP(*, T, a, x * a, y * a) OP(/, T, a, x / a, y / a) friend pt operator * (T a, ref p) { return pt(a * p.x, a * p.y); } bool operator < (ref p) const { return eq(x, p.x) ? lt(y, p.y) : lt(x, p.x); } CMP(<=, !(p < *this)) CMP(>, p < *this) CMP(>=, !(*this < p)) CMP(==, !(*this < p) && !(p < *this)) CMP(!=, *this < p || p < *this) OP(*, ref, p, x * p.x - y * p.y, y * p.x + x * p.y) OP(/, ref, p, (x * p.x + y * p.y) / (p.x * p.x + p.y * p.y), (y * p.x - x * p.y) / (p.x * p.x + p.y * p.y)) }; #undef OP #undef CMP istream &operator >> (istream &stream, pt &p) { return stream >> p.x >> p.y; } ostream &operator << (ostream &stream, ref p) { return stream << p.x << ' ' << p.y; } pt conj(ref a) { return pt(a.x, -a.y); } T dot(ref a, ref b) { return a.x * b.x + a.y * b.y; } T cross(ref a, ref b) { return a.x * b.y - a.y * b.x; } T norm(ref a) { return dot(a, a); } T abs(ref a) { return sqrt(norm(a)); } T arg(ref a) { return atan2(a.y, a.x); } pt polar(T r, T theta) { return r * pt(cos(theta), sin(theta)); } T distSq(ref a, ref b) { return norm(b - a); } T dist(ref a, ref b) { return abs(b - a); } T ang(ref a, ref b) { return arg(b - a); } // sign of ang, area2, ccw: 1 if counterclockwise, 0 if collinear, // -1 if clockwise T ang(ref a, ref b, ref c) { return remainder(ang(b, a) - ang(b, c), 2 * acos(T(-1))); } // twice the signed area of triangle a, b, c T area2(ref a, ref b, ref c) { return cross(b - a, c - a); } int ccw(ref a, ref b, ref c) { return sgn(area2(a, b, c)); } // a rotated theta radians around p pt rot(ref a, ref p, T theta) { return (a - p) * pt(polar(T(1), theta)) + p; } // rotated 90 degrees ccw pt perp(ref a) { return pt(-a.y, a.x); } struct DecrementalUpperHull { struct Link; using ptr = Link *; struct Link { int id; pt p; ptr prv, nxt; Link(int id, ref p) : id(id), p(p), prv(nullptr), nxt(nullptr) {} }; struct Node { ptr chain, back, tangent; Node() : chain(nullptr), back(nullptr), tangent(nullptr) {} }; int N; vector<Node> TR; vector<Link> links; template <class F, class G> pair<ptr, ptr> findBridge(ptr l, ptr r, F f, G g) { while (f(l) || f(r)) { if (!f(r) || (f(l) && g(pt(0, 0), f(l)->p - l->p, f(r)->p - r->p))) { if (g(l->p, f(l)->p, r->p)) l = f(l); else break; } else { if (!g(l->p, r->p, f(r)->p)) r = f(r); else break; } } return make_pair(l, r); } void fixChain(int x, ptr l, ptr r, bool rev) { if (rev) { tie(r, l) = findBridge(r, l, [&] (ptr q) { return q->prv; }, [&] (ref a, ref b, ref c) { return ccw(a, b, c) >= 0; }); } else { tie(l, r) = findBridge(l, r, [&] (ptr q) { return q->nxt; }, [&] (ref a, ref b, ref c) { return ccw(a, b, c) <= 0; }); } TR[x].tangent = l; TR[x].chain = TR[x * 2].chain; TR[x].back = TR[x * 2 + 1].back; TR[x * 2].chain = l->nxt; TR[x * 2 + 1].back = r->prv; if (l->nxt) l->nxt->prv = nullptr; else TR[x * 2].chain = nullptr; if (r->prv) r->prv->nxt = nullptr; else TR[x * 2 + 1].chain = nullptr; l->nxt = r; r->prv = l; } void build(int x, int tl, int tr) { if (tl == tr) { TR[x].chain = TR[x].back = &links[tl]; return; } int m = tl + (tr - tl) / 2; build(x * 2, tl, m); build(x * 2 + 1, m + 1, tr); fixChain(x, TR[x * 2].chain, TR[x * 2 + 1].chain, false); } void rob(int x, int y) { TR[x].chain = TR[y].chain; TR[x].back = TR[y].back; TR[y].chain = TR[y].back = nullptr; } void rem(int x, int tl, int tr, int i) { if (i < tl || tr < i) return; int m = tl + (tr - tl) / 2, y = x * 2 + int(i > m); if (!TR[x].tangent) { TR[y].chain = TR[x].chain; TR[y].back = TR[x].back; if (i <= m) rem(x * 2, tl, m, i); else rem(x * 2 + 1, m + 1, tr, i); rob(x, y); return; } ptr l = TR[x].tangent, r = l->nxt; l->nxt = TR[x * 2].chain; if (TR[x * 2].chain) TR[x * 2].chain->prv = l; else TR[x * 2].back = l; TR[x * 2].chain = TR[x].chain; r->prv = TR[x * 2 + 1].back; if (TR[x * 2 + 1].back) TR[x * 2 + 1].back->nxt = r; else TR[x * 2 + 1].chain = r; TR[x * 2 + 1].back = TR[x].back; if (TR[y].chain == TR[y].back && TR[y].chain->id == i) { TR[y].chain = TR[y].back = nullptr; rob(x, y ^ 1); TR[x].tangent = nullptr; return; } if (i <= m) { if (l->id == i) l = l->nxt; rem(x * 2, tl, m, i); if (!l) l = TR[x * 2].back; } else { if (r->id == i) r = r->prv; rem(x * 2 + 1, m + 1, tr, i); if (!r) r = TR[x * 2 + 1].chain; } fixChain(x, l, r, i <= m); } void rem(int i) { if (TR[1].chain == TR[1].back) { TR[1].chain = TR[1].back = nullptr; return; } rem(1, 0, N - 1, i); } DecrementalUpperHull(const vector<pt> &P) : N(P.size()), TR(N == 0 ? 0 : 1 << __lg(N * 4 - 1)) { links.reserve(N); for (int i = 0; i < N; i++) links.emplace_back(i, P[i]); build(1, 0, N - 1); } vector<int> getHull() { vector<int> ret; for (ptr x = TR[1].chain; x; x = x->nxt) ret.push_back(x->id); return ret; } }; vector<int> convexLayers(const vector<pt> &P) { if (P.empty()) return vector<int>(); int N = P.size(); vector<int> ind(N); iota(ind.begin(), ind.end(), 0); sort(ind.begin(), ind.end(), [&] (int i, int j) { return P[i] < P[j]; }); vector<pt> tmp(N); for (int i = 0; i < N; i++) tmp[i] = P[ind[i]]; DecrementalUpperHull up(tmp); for (int i = 0; i < N; i++) tmp[i] = P[ind[N - i - 1]] * T(-1); DecrementalUpperHull down(move(tmp)); vector<int> ret(N, -1); for (int layer = 0, done = 0; done < N; layer++) { vector<int> hull; for (int i : up.getHull()) hull.push_back(i); for (int i : down.getHull()) hull.push_back(N - i - 1); for (int i : hull) if (ret[ind[i]] == -1) { ret[ind[i]] = layer; done++; up.rem(i); down.rem(N - i - 1); } } return ret; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector<pt> P(N); for (auto &&p : P) cin >> p; for (int layer : convexLayers(P)) cout << (layer + 1) << nl; return 0; }