消失吧，群青

冷却心 · 2025-11-04 13:10:16 · 题解

发现时刻和位置可以非整数很难处理，由于精度要求不高，我们把时间和长度尺度全部乘以 10^k，只考虑在整数情况，最后把答案除以 10^k，这样数值上能近似求出在任意时刻都可以转弯的答案，这里 k 取 3 足够了。

二分答案 d。把流星按照时间排序。发现每个时刻能到达的点集是一些区间的并，我们用一个 set 维护这些区间，时间经过 t 会让这些区间的左右端点各延伸 t 单位长度，并合并相邻有交的区间，在坐标 x 上落下流星等于该时刻不能位于 [x-d+1,x+d-1]，需要点集内在该区间内的点删除。删除操作就类似 ODT 直接可以做完，每次暴力延伸区间时间复杂度不可行，所以我们给每个区间再带上一个标记表示上次被更新的时刻，删除操作只关心和 [x-d+1,x+d-1] 有交的区间，我们只更新左右端点前后的区间即可。然后做完了，复杂度 O(n\log n\log V)。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n; pair<LL, LL> A[N];

struct Info { LL l, r, t; };
const bool operator<(const Info a, const Info b) {
    return (a.l != b.l ? a.l < b.l : (a.r != b.r ? a.r < b.r : a.t < b.t));
}
set<Info> s;
void upd(Info x, LL t) {
    auto it = s.find(x);
    if (it == s.end()) return ;
    auto [l, r, t0] = *it; r += t - t0; l -= t - t0; it = s.erase(it);
    while (it != s.end() && it->l - r <= t - it->t)
        r = max(r, it->r + t - it->t), it = s.erase(it);
    while (it != s.begin()) {
        it = prev(it); if (l - it->r > t - it->t) break;
        l = min(l, it->l - t + it->t); it = s.erase(it);
    }
    s.insert({l, r, t});
}
void upd(LL x, LL t) {
    auto it = s.lower_bound({x + 1, 0, 0}); upd(*it, t);
    it = s.lower_bound({x + 1, 0, 0}); if (it != s.begin()) upd(*prev(it), t);
}
bool check(LL d) {
    if (d == 0) return true;
    s.clear(); s.insert({0, 0, 0});
    for (int i = 1; i <= n; i ++) {
        if (s.empty()) return false;
        auto [cur, x] = A[i];
        LL l = x - d + 1, r = x + d - 1;
        upd(r, cur); upd(l, cur);  
        auto it = s.lower_bound({l + 1, 0, 0}); 
        if (it != s.begin() && prev(it)->r >= l) {
            auto [a, b, c] = *prev(it); s.erase(prev(it));
            if (a < l) s.insert({a, l - 1, c});
            if (b > r) { s.insert({r + 1, b, c}); continue; }
        }
        while (it != s.end() && it->l <= r) {
            auto [a, b, c] = *it; it = s.erase(it);
            if (b > r) { s.insert({r + 1, b, c}); break; }
        }
    }
    return !s.empty();
}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n; const ull K = 1000;
    for (int i = 1, t, x; i <= n; i ++)
        cin >> t >> x, A[i] = {1ll * t * K, 1ll * x * K};
    sort(A + 1, A + 1 + n);
    LL L = 0, R = 1e13;
    while (L + 1 < R) {
        LL mid = (L + R) >> 1;
        if (check(mid)) L = mid;
        else R = mid;
    }
    cout << fixed << setprecision(1) << (double)L / K << "\n";
    return 0;
}