#include <bits/stdc++.h>
#define blue 0
#define red 1
#define purple 2
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
using namespace std;
typedef long long ll;
typedef long double ld;
struct node {
ld l, r;
int f;
node() {}
node(ld l, ld r, ll f) : l(l), r(r), f(f) {}
};
const int N = 1e6 + 500;
const ld eps = 1e-9;
node t[4 * N];
int D[4 * N];
vector <ld> lft, rgt;
ll x[N], y[N];
int n, h, f[N];
void push(int v) {
if (D[v] != 1e9) {
D[v * 2] = min(D[v * 2], D[v]);
D[v * 2 + 1] = min(D[v * 2 + 1], D[v]);
t[v].f = min(t[v].f, D[v]);
D[v] = 1e9;
}
}
void build(int v, int l, int r) {
D[v] = 1e9;
if (l == r) {
t[v] = node(lft[l], rgt[l], 1e9);
} else {
int md = (l + r) >> 1;
build(v * 2, l, md);
build(v * 2 + 1, md + 1, r);
t[v].f = min(t[v * 2].f, t[v * 2 + 1].f);
t[v].l = max(t[v * 2].l, t[v * 2 + 1].l);
t[v].r = min(t[v * 2].r, t[v * 2 + 1].r);
}
}
ll getl(int v, int l, int r, int tl, int tr) {
if (l > r || tl > tr || tl > r || l > tr) {
return -1e18;
}
if (l >= tl && r <= tr) {
return t[v].l;
}
int md = (l + r) >> 1;
return max(getl(v * 2, l, md, tl, tr), getl(v * 2 + 1, md + 1, r, tl, tr));
}
ll getr(int v, int l, int r, int tl, int tr) {
if (l > r || tl > tr || tl > r || l > tr) {
return 1e18;
}
if (l >= tl && r <= tr) {
return t[v].r;
}
int md = (l + r) >> 1;
return min(getr(v * 2, l, md, tl, tr), getr(v * 2 + 1, md + 1, r, tl, tr));
}
ll getf(int v, int l, int r, int ps) {
push(v);
if (l == r) {
return t[v].f;
} else {
int md = (l + r) >> 1, cur;
if (ps <= md) {
return getf(v * 2, l, md, ps);
} else {
return getf(v * 2 + 1, md + 1, r, ps);
}
}
}
void upd(int v, int l, int r, int tl, int tr, int val) {
push(v);
if (l > r || tl > tr || tl > r || l > tr) {
return;
}
if (l >= tl && r <= tr) {
D[v] = min(D[v], val);
push(v);
return;
}
int md = (l + r) >> 1;
upd(v * 2, l, md, tl, tr, val);
upd(v * 2 + 1, md + 1, r, tl, tr, val);
}
int main() {
cerr.precision(9);
cerr << fixed;
cin >> n >> h;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
// if (n == 3) {
// cout << "0";
// return 0;
// }
for (int i = 3; i < n; i += 2) {
ld k = ld(y[i - 1] - y[i]) / ld(x[i - 1] - x[i]);
ld b = ld(y[i]) - k * x[i];
// cerr << k << " " << b << el;
lft.pb((h - b) / k);
k = ld(y[i] - y[i + 1]) / ld(x[i] - x[i + 1]);
b = ld(y[i]) - k * x[i];
// cerr << k << " " << b << el;
rgt.pb((h - b) / k);
}
n >>= 1; n--;
lft.pb(-1e18);
lft.pb(-1e18);
build(1, 0, n);
f[0] = 0;
upd(1, 0, n, 0, 0, 0);
for (int i = 0; i < n; i++) {
int l = 0;
int r = n - i;
f[i] = getf(1, 0, n, i);
while (l < r) {
int md = (l + r + 1) >> 1;
// cerr << getl(1, 0, n + 1, i, i + md) << " " << getr(1, 0, n + 1, i, i + md) << "\n";
if (getl(1, 0, n, i, i + md) < getr(1, 0, n, i, i + md) + eps) {
l = md;
} else {
r = md - 1;
}
}
upd(1, 0, n, i + 1, i + r + 1, f[i] + 1);
}
cout << getf(1, 0, n, n);
}
Compilation message
Main.cpp: In function 'll getf(int, int, int, int)':
Main.cpp:82:32: warning: unused variable 'cur' [-Wunused-variable]
82 | int md = (l + r) >> 1, cur;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
