使用叉积求凸包,使用差分约束求线段覆盖,用拓扑排序求差分约束。
#ifdef LOCAL_TEST
#include "D:/C++/include/all.h"
#else
#define debug(...)
#define cpp_version_ __cplusplus
#endif
#include <bits/stdc++.h>
#undef cpp_version_
using namespace std;
using bool_t = unsigned char;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
void fast_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
template <typename T> void ckmax(T &a, T b) {
if (a < b) a = b;
}
template <typename T> void ckmin(T &a, T b) {
if (b < a) a = b;
}
constexpr f64 eps = 1e-6;
struct Point {
int x, y;
Point operator-(const Point& o) const {
return {x - o.x, y - o.y};
}
};
using Vec = Point;
i64 Cross(const Vec& a, const Vec& b) {
return static_cast<i64>(a.x) * b.y - static_cast<i64>(a.y) * b.x;
}
void solve() {
int N, H;
cin >> N >> H;
vector<Point> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i].x >> a[i].y;
}
vector<pair<f64, f64>> b((N >> 1) - 1);
vector<Point> ch;
u32 ch_len = 0;
int cnt = 0;
Point this_p;
for (int i = 0; i < N; ++i) {
this_p = a[i];
while (ch_len > 1 && Cross(ch[ch_len - 1] - ch[ch_len - 2], this_p - ch[ch_len - 1]) >= 0) {
ch.pop_back();
--ch_len;
}
if (!(i & 1) && i != 0 && i != N - 1) {
b[cnt++].first = this_p.x - (this_p.x - ch[ch_len - 1].x) * (H - this_p.y) / static_cast<f64>(ch[ch_len - 1].y - this_p.y);
}
ch.push_back(this_p);
++ch_len;
}
ch.clear(); ch_len = 0; cnt = (N >> 1) - 1;
for (int i = N - 1; i >= 0; --i) {
this_p = a[i];
while (ch_len > 1 && Cross(ch[ch_len - 1] - ch[ch_len - 2], this_p - ch[ch_len - 1]) <= 0) {
ch.pop_back();
--ch_len;
}
if (!(i & 1) && i != 0 && i != N - 1) {
b[--cnt].second = this_p.x + (ch[ch_len - 1].x - this_p.x) * (H - this_p.y) / static_cast<f64>(ch[ch_len - 1].y - this_p.y);
}
ch.push_back(this_p);
++ch_len;
}
vector<f64> nums;
for (const auto& p : b) {
nums.push_back(p.first);
nums.push_back(p.second);
}
sort(nums.begin(), nums.end());
nums.resize(N = unique(nums.begin(), nums.end(), [](f64 a, f64 b) {return fabs(a - b) < eps;}) - nums.begin());
vector<vector<pair<int, int>>> g(N + 1);
pair<int, int> range;
for (const auto& p : b) {
range = {
lower_bound(nums.begin(), nums.end(), p.first, [](f64 a, f64 b){return a - b < -eps;}) - nums.begin() + 1,
lower_bound(nums.begin(), nums.end(), p.second, [](f64 a, f64 b){return a - b < -eps;}) - nums.begin() + 1
};
g[range.first - 1].emplace_back(range.second, 1);
}
vector<int> dist(N + 1, 0);
for (int i = 0; i < N; ++i) {
g[i].emplace_back(i + 1, 0);
for (const auto& [v, w] : g[i]) {
ckmax(dist[v], dist[i] + w);
}
}
cout << dist[N] << '\n';
}
int main() {
fast_io();
int T = 1;
// cin >> T;
while (T--) {
solve();
#ifdef LOCAL_TEST
cout << flush;
// cerr << endl;
#endif
}
return 0;
}