自动搬运

查看原文

来自洛谷，原作者为

	tribool4_in chr(81)

搬运于2025-08-24 21:27:58，当前版本为作者最后更新于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;
}