题解：P13511 [KOI 2025 #1] 直角等腰三角形

· · 题解

题意分析

在直角坐标系上有一些点，我们需要找出所有包含着这些点的等腰直角三角形中斜边最短的，并且等腰直角三角形的斜边必须与Y轴平行。

解题思路

首先我们发现，由于斜边与Y轴平行，为了包裹住所有的点，我们的斜边一定在所有点中Y坐标最大（或最小）的点所在的直线。此外，题目还给了我们一些图片来帮助我们解题： 如图所示，因为等腰直角三角形的两个锐角是45°，并且斜边与Y轴平行，所以两条直角边上的点 （x，y） 一定满足 x+y 的值一定或者 y-x 的值一定。
因为我们要求的是最小值，所以我们可以先分别找出最大的 x+y、最大的 y-x 和最小的Y坐标，然后再以最大的 x+y 和最大的 y-x 作直角边，以最小的Y坐标作斜边，两条直角边与斜边的两个交点X坐标之差就是最小的斜边长度（以上仅包括正三角，倒三角同理，只不过是最小的 x+y 和 y-x，最大的Y坐标）
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x[114514],y[114514],n,maxi=-1e18,mini=1e18;
ll maxa=-1e18,mina=1e18,maxb=-1e18,minb=1e18;//题目中的范围是-1e8~1e8，所以最大值要设到负数 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>x[i]>>y[i];
        maxi=max(maxi,y[i]);
        mini=min(mini,y[i]);

        maxa=max(maxa,x[i] + y[i]);//求最大的x+y

        maxb=max(maxb,y[i] - x[i]);//求最大的y-x

        mina=min(mina,x[i] + y[i]);//求最小的x+y

        minb=min(minb,y[i] - x[i]);//求最小的y-x
    }//求的过程不要弄混了，赛中就是因为一个x和y反了炸掉60多分 
    cout<<min(abs((maxa-mini)-(mini-maxb)),abs((maxi-minb)-(maxi-mina)));

    return 0;
}