[KOI 2025 #1] 直角等腰三角形

· · 题解

子问题 3

作为答案的直角等腰三角形，可以分为其直角顶点位于斜边上方和下方两种情况。对每种情况分别计算斜边长度的最小值，然后输出两者中较小的值即可。

我们设连接直角等腰三角形斜边的两个端点为 (a, c) 和 (b, c)。（a < b）由于给定的所有点的 x, y 坐标的绝对值最大为 30，因此不需要考虑 |a|, |b| > 90, |c| > 30 的三角形。因此，只需对所有满足该条件的直角等腰三角形，检查其是否包含所有给定的点即可。这可以通过多边形内点判断等多种方法实现，但也可以利用以下的观察结论。

设一个直角等腰三角形的斜边端点为 (a,c), (b,c)（a<b），且其直角顶点位于斜边上方，那么该三角形包含点 (x,y) 的条件如下：

利用上述条件，我们可以在 O(N) 时间内判断某个直角等腰三角形是否包含所有给定的点。因此，如果输入点的坐标的绝对值最大为 X，那么总时间复杂度为 O(X^3N)。

子问题 4

可以发现，满足条件且斜边长度最小的直角等腰三角形，其每条边上都至少包含一个给定的点。（可以认为，这也包括了边的端点恰好是给定点之一的情况。）

我们先只考虑直角顶点在斜边上方的情况。如果我们在直角等腰三角形的每条边上各选一个点，就可以确定该三角形的三个顶点。因此，对于选择三个点的 N^3 种情况，可以确定一个直角等腰三角形。然后，可以利用子问题 3 的解法，检查该三角形是否包含所有 N 个点，从而解决问题。直角顶点在斜边下方的情况，可以用同样的方法解决。

总时间复杂度为 O(N^4)。此外，还存在多种其他多项式时间复杂度的解法来解决该子问题。

子问题 5

在此子问题中，所有给定点的 y 坐标都相同。在这种情况下，最优解是让所有点都位于直角等腰三角形的斜边上。因此，给定点的 x 坐标的最大值与最小值之差即为斜边的长度，也就是答案。

子问题 6

在此子问题中，所有给定点都位于直线 y=x 上。在这种情况下，最优解是让所有点都位于直角等腰三角形的一条直角边（非斜边）上。因此，作为答案的直角等腰三角形的两个顶点，是给定点中 x 坐标最小的点和最大的点。由此可以求出剩下的一个顶点以及斜边的长度。

子问题 7

我们先只考虑直角顶点在斜边上方的情况。

假设作为答案的直角等腰三角形，其斜边的右端点坐标为 (d,0)。由于该三角形斜边的中点是 (0,0)，因此连接斜边的两个顶点的坐标是 (-d, 0) 和 (d, 0)，斜边长度为 2d。

如果一个斜边长度为 2d 的直角等腰三角形包含了所有给定的点，那么对于所有 d' > d，一个斜边长度为 2d' 的直角等腰三角形也必然包含所有给定的点。

因为需要求斜边长度的最小值，所以可以通过对 d 进行二分搜索来求出其最小值。对于一个固定的 d，以 (-d, 0) 和 (d,0) 为（斜边）顶点的直角等腰三角形是否包含所有点，可以使用子问题 3 的解法来判断。

用同样的方法，也可以求出直角顶点在斜边下方情况时斜边长度的最小值。如果两种情况都可行，则输出两个斜边长度中较小的一个；如果只有一种情况可行，则输出该情况下的斜边长度。

子问题 8

我们只考虑直角顶点在斜边上方的情况。在这类三角形中，我们设斜边长度最小的三角形，其斜边的两个端点为 (a, c) 和 (b, c)。（a < b）

设所有给定点的 y 坐标的最小值为 m。根据子问题 3 的条件，所有给定点的 y 坐标都必须大于或等于 c。即，m \ge c。如果 m > c，斜边将不包含 N 个给定点中的任何一个，这与子问题 4 中的观察相矛盾。因此，我们只需考虑 m = c 的情况。

由于 c 的值已经确定，我们可以根据子问题 3 的条件求出 a 的最大值和 b 的最小值。我们需要最小化斜边长度 b-a，因此上述两个值（b 的最小值和 a 的最大值）之差就是答案。

直角顶点在斜边下方的情况，也可以用同样的方法解决。

总时间复杂度为 O(N)。

/*
* 2025 KOI 抗急
* 檬殿何 2锅
*/
#include <bits/stdc++.h>
using namespace std;
#define MAX 100'010
int X[100'010];
int Y[100'010];
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int N;
    cin >> N;
    int i;
    int minY = 2e9, maxY = -2e9;
    for (i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
        minY = min(minY, Y[i]);
        maxY = max(maxY, Y[i]);
    }
    int ans = 2e9;

    int minv = 2e9, maxv = -2e9;
    for (i = 1; i <= N; i++) {
        maxv = max(maxv, X[i] + Y[i]);
        minv = min(minv, X[i] - Y[i]);
    }
    ans = min(ans, (maxv - minY) - (minY + minv));

    minv = 2e9, maxv = -2e9;
    for (i = 1; i <= N; i++) {
        maxv = max(maxv, X[i] - Y[i]);
        minv = min(minv, X[i] + Y[i]);
    }
    ans = min(ans, (maxY + maxv) - (minv - maxY));
    cout << ans;
}