P2600 [ZJOI2008]瞭望塔 题解

· · 题解

Update 2020/12/27 修复了一点锅。 Update 2020/12/28 删除了不必要的预编译指令。

题目大意

前置知识

  1. 半平面交

解法

  1. 对于折线上任一一段，该点能看到其端点仅当该点在该线段所在直线的上方。
  2. 求出所有满足（1）的半平面的交集，显然，这是一个下凸壳。
  3. 假设存在一个下凸壳上的点 A 与一个折点 B ，使得其连线与折线相交。分情况讨论。
    1. 交于折点 C （显然 B C 不相邻）， 易知 B C 中折线中必有不满足假设者。
    2. 交于折线 CD , 易知 B C 中折线中必有不满足假设者。
  4. 如下图（画技不好，请见谅）,灰色部分为下凸壳，枚举下凸壳与原折线的折点，可求此时两者间的距离。取min即可。

代码

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define pss pair<string, string>
typedef long long ll;
typedef long double ldb;
ldb ASDF , FGHJ;
#define MAX(a, b) (ASDF = (a)) < (FGHJ = (b)) ? FGHJ : ASDF
#define MIN(a, b) (ASDF = (a)) > (FGHJ = (b)) ? FGHJ : ASDF
const ldb eps = 1e-9;
const int MAXN = 307;
using namespace std;

int N;
struct Node {
    ldb x, y;
    bool operator<(Node b) { return x < b.x; }
} a[MAXN], c[MAXN];
struct line {
    ldb k, b;
    bool operator<(line g) { return k < g.k || (k == g.k && b > g.b); }
} e[MAXN];
int now;
int stk[MAXN], tp;
inline line make_line(Node a, Node b) {  // a.x != b.x
    register line res;
    res.k = (b.y - a.y) / (b.x - a.x);
    res.b = a.y - res.k * a.x;
    return res;
}
inline Node intersect(line a, line b) {
    register Node res;
    res.x = (a.b - b.b) / (b.k - a.k);
    res.y = a.k * res.x + a.b;
    return res;
}
ldb ans = 1e50;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    For(i, 1, N) cin >> a[i].x;
    For(i, 1, N) cin >> a[i].y;
    For(i, 1, N - 1) e[i] = make_line(a[i], a[i + 1]);
    sort(e + 1, e + N);
    now = 1;
    For(i, 2, N - 1) if (e[i].k > e[now].k) e[++now] = e[i];
    For(i, 1, now) {
        while (tp > 1 && (e[i].b - e[stk[tp - 1]].b) * (-e[stk[tp]].k + e[stk[tp - 1]].k) <
                             (e[stk[tp]].b - e[stk[tp - 1]].b) * (-e[i].k + e[stk[tp - 1]].k))
            tp--;
        stk[++tp] = i;
    }
    For(i, 1, tp - 1) {
        c[i] = intersect(e[stk[i]], e[stk[i + 1]]);
        if (c[i].x > a[N].x || c[i].x < a[1].x)
            continue;
        register int w = lower_bound(a + 1, a + N + 1, c[i]) - a;
        register line m = make_line(a[w], a[w - 1]);
        ans = MIN(ans, c[i].y - m.k * c[i].x - m.b);
    }
    For(i, 1, N) {
        register int w = lower_bound(c + 1, c + tp, a[i]) - c;
        ans = MIN(ans, e[stk[w]].k * a[i].x + e[stk[w]].b - a[i].y);
    }
    cout << fixed << setprecision(3) << ans + eps << endl;//注意精度！
    return 0;
}