제출 #375851

#제출 시각아이디문제언어결과실행 시간메모리
375851wleung_bvgPlanine (COCI21_planine)C++17
30 / 110
2068 ms58332 KiB
#include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;using ld=long double;constexpr const char nl='\n',sp=' '; 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 x real() #define y imag() #define ref const pt & using pt = complex<T>; istream &operator >> (istream &stream, pt &p) { T X, Y; stream >> X >> Y; p = pt(X, Y); return stream; } ostream &operator << (ostream &stream, ref p) { return stream << p.x << ' ' << p.y; } bool operator < (ref a, ref b) { return eq(a.x, b.x) ? lt(a.y, b.y) : lt(a.x, b.x); } bool operator <= (ref a, ref b) { return !(b < a); } bool operator > (ref a, ref b) { return b < a; } bool operator >= (ref a, ref b) { return !(a < b); } bool operator == (ref a, ref b) { return !(a < b) && !(b < a); } bool operator != (ref a, ref b) { return a < b || b < a; } struct pt_lt { bool operator () (ref a, ref b) const { return a < b; } }; struct pt_le { bool operator () (ref a, ref b) const { return !(b < a); } }; struct pt_gt { bool operator () (ref a, ref b) const { return b < a; } }; struct pt_ge { bool operator () (ref a, ref b) const { return !(a < b); } }; struct pt_eq { bool operator () (ref a, ref b) const { return !(a < b) && !(b < a); } }; struct pt_ne { bool operator () (ref a, ref b) const { return a < b || b < a; } }; // abs gets polar distance, arg gets polar angle 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 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 Line { pt v; T c; // ax + by = c, left side is ax + by >= c Line(T a = 0, T b = 0, T c = 0) : v(b, -a), c(c) {} // direction vector v with offset c Line(ref v, T c) : v(v), c(c) {} // points p and q Line(ref p, ref q) : v(q - p), c(cross(v, p)) {} T eval(ref p) const { return cross(v, p) - c; } // 1 if left of line, 0 if on line, -1 if right of line int onLeft(ref p) const { return sgn(eval(p)); } T distSq(ref p) const { T e = eval(p); return e * e / norm(v); } T dist(ref p) const { return abs(eval(p) / abs(v)); } // rotated 90 degrees ccw Line perpThrough(ref p) const { return Line(p, p + perp(v)); } Line translate(ref p) const { return Line(v, c + cross(v, p)); } Line shiftLeft(T d) const { return Line(v, c + d * abs(v)); } pt proj(ref p) const { return p - perp(v) * eval(p) / norm(v); } pt refl(ref p) const { return p - perp(v) * T(2) * eval(p) / norm(v); } // compares points by orthogonal projection (3 way comparison) int cmpProj(ref p, ref q) const { return sgn(dot(v, p) - dot(v, q)); } }; int lineLineIntersection(const Line &l1, const Line &l2, pt &res) { T d = cross(l1.v, l2.v); if (eq(d, 0)) return pt_eq()(l2.v * l1.c, l1.v * l2.c) ? 2 : 0; res = (l2.v * l1.c - l1.v * l2.c) / d; return 1; } template <class T, class Cmp = less<T>> vector<pair<T, T>> &maxDisjointIntervals(vector<pair<T, T>> &A, Cmp cmp = Cmp()) { sort(A.begin(), A.end(), [&] (const pair<T, T> &a, const pair<T, T> &b) { return cmp(a.second, b.second); }); int i = 0; for (int l = 0, r = 0, N = A.size(); l < N; l = r, i++) { A[i] = A[l]; for (r = l = 1; r < N && !cmp(A[i].second, A[r].first); r++); } A.erase(A.begin() + i, A.end()); return A; } const bool FIRST = true, LAST = false; template <const bool ISFIRST, class T, class F> T bsearch(T lo, T hi, F f) { static_assert(is_integral<T>::value, "T must be integral"); hi--; while (lo <= hi) { T mid = lo + (hi - lo) / 2; if (f(mid) == ISFIRST) hi = mid - 1; else lo = mid + 1; } return ISFIRST ? lo : hi; } 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; ld H; cin >> N >> H; Line l(pt(0, H), pt(1, H)); vector<pt> P(N); for (auto &&p : P) cin >> p; vector<pair<T, T>> intervals; for (int i = 2; i < N - 2; i += 2) intervals.emplace_back(0, 0); vector<pt> hull; for (int i = 1; i < N - 2; i++) { if (i % 2) { while (sz(hull) >= 2 && ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i]) >= 0) hull.pop_back(); hull.push_back(P[i]); } else { int j = bsearch<FIRST>(0, sz(hull) - 1, [&] (int k) { return ccw(hull[k], hull[k + 1], P[i]) > 0; }); pt p; lineLineIntersection(l, Line(hull[j], P[i]), p); intervals[i / 2 - 1].first = p.x; } } hull.clear(); for (int i = N - 2; i >= 2; i--) { if (i % 2) { while (sz(hull) >= 2 && ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i]) <= 0) hull.pop_back(); hull.push_back(P[i]); } else { int j = bsearch<FIRST>(0, sz(hull) - 1, [&] (int k) { return ccw(hull[k], hull[k + 1], P[i]) < 0; }); pt p; lineLineIntersection(l, Line(hull[j], P[i]), p); intervals[i / 2 - 1].second = p.x; } } cout << sz(maxDisjointIntervals(intervals, eps_lt())) << nl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...