题解：P1691 [ICPC2016 WF] Oil

tribool4_in · 2024-04-02 18:44:27 · 题解

题意理解：油井（直线）不一定垂直于地面，可以是倾斜的，只要不平行于地面就行。

发现 n\le 2000，端点个数为 O(n)，考虑 O(n^2) 枚举端点以确定直线。容易发现一个性质：经过两条线段端点上的直线一定可以成为最优解。证明考虑对于一条最优解直线，将其平移至与某个端点相交；然后绕着此点旋转直到与另一个端点相交。此时得到的直线的答案与原来相同。

发现直接枚举两个端点无法求出其经过的线段权值和。于是考虑 O(n) 枚举其中一个端点，由其斜率即可确定直线。此时对于所有与其不在同一高度的线段，与之有交的直线斜率构成一段区间。于是问题转化为有若干个带权区间 [k_l,k_r]，找出一个位置使得覆盖它的区间权值和最大。O(n) 求出这些区间，排序然后扫一遍即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const double eps = 1e-7;
int n;
struct line {
    int x1, x2, y;
} l[N];
#define k(x1, y1, x2, y2) (1.0 * ((x2) - (x1)) / ((y2) - (y1)))
vector<pair<double, int>> ud;
int calc(int x0, int y0) {
    ud.clear();
    for (int i = 1; i <= n; i++) {
        if (l[i].y == y0) continue;
        double k1 = k(x0, y0, l[i].x1, l[i].y), k2 = k(x0, y0, l[i].x2, l[i].y);
        if (k1 > k2) swap(k1, k2);
        ud.emplace_back(k1, abs(l[i].x2 - l[i].x1)), ud.emplace_back(k2 + eps, -abs(l[i].x2 - l[i].x1));
    }
    sort(ud.begin(), ud.end());
    int cur = 0, ans = 0;
    for (auto [k, v] : ud) {
        cur += v;
        ans = max(ans, cur);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> l[i].x1 >> l[i].x2 >> l[i].y;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, calc(l[i].x1, l[i].y) + abs(l[i].x2 - l[i].x1));
        ans = max(ans, calc(l[i].x2, l[i].y) + abs(l[i].x2 - l[i].x1));
    }
    cout << ans << '\n';
    return 0;
}