#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 a <= b; } };
struct pt_gt { bool operator () (ref a, ref b) const { return a > b; } };
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; } };
struct pt_ne { bool operator () (ref a, ref b) const { return a != b; } };
// 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)));
}
// 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
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); }
};
int lineIntersection(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 It,
class Cmp = less<typename iterator_traits<It>::value_type::first_type>>
It maxDisjointIntervals(It st, It en, Cmp cmp = Cmp()) {
using Pair = typename iterator_traits<It>::value_type;
assert(is_sorted(st, en, [&] (const Pair &a, const Pair &b) {
return cmp(a.second, b.second);
}));
It cur = st; for (It l = st, r = st; l != en; l = r, cur++) {
*cur = *l; for (r = l + 1; r != en && !cmp(cur->second, r->first); r++);
}
return cur;
}
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;
lineIntersection(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;
lineIntersection(l, Line(hull[j], P[i]), p);
intervals[i / 2 - 1].second = p.x;
}
}
vector<pair<T, T>> tmp = intervals;
sort(intervals.begin(), intervals.end(), [&] (const pair<T, T> &a, const pair<T, T> &b) {
return lt(a.second, b.second);
});
cout << maxDisjointIntervals(intervals.begin(), intervals.end(), eps_lt()) - intervals.begin() << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1136 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1136 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1136 KB |
Output is correct |
| 4 |
Correct |
70 ms |
6756 KB |
Output is correct |
| 5 |
Correct |
73 ms |
6756 KB |
Output is correct |
| 6 |
Correct |
79 ms |
6756 KB |
Output is correct |
| 7 |
Correct |
745 ms |
63124 KB |
Output is correct |
| 8 |
Correct |
757 ms |
63036 KB |
Output is correct |
| 9 |
Correct |
787 ms |
63164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1136 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1136 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1136 KB |
Output is correct |
| 4 |
Correct |
70 ms |
6756 KB |
Output is correct |
| 5 |
Correct |
73 ms |
6756 KB |
Output is correct |
| 6 |
Correct |
79 ms |
6756 KB |
Output is correct |
| 7 |
Correct |
745 ms |
63124 KB |
Output is correct |
| 8 |
Correct |
757 ms |
63036 KB |
Output is correct |
| 9 |
Correct |
787 ms |
63164 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
2 ms |
492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
741 ms |
63152 KB |
Output is correct |
| 18 |
Correct |
785 ms |
63164 KB |
Output is correct |
| 19 |
Correct |
82 ms |
6756 KB |
Output is correct |
| 20 |
Correct |
769 ms |
63152 KB |
Output is correct |
| 21 |
Correct |
77 ms |
6756 KB |
Output is correct |
| 22 |
Correct |
819 ms |
63036 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
804 ms |
63164 KB |
Output is correct |
| 25 |
Correct |
83 ms |
6756 KB |
Output is correct |
| 26 |
Correct |
858 ms |
63164 KB |
Output is correct |
| 27 |
Correct |
36 ms |
3560 KB |
Output is correct |
