题意分析

在直角坐标系上有一些点，我们需要找出所有包含着这些点的等腰直角三角形中斜边最短的，并且等腰直角三角形的斜边必须与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代码：

CPP

#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;
}

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

文章操作

题意分析

解题思路

相关推荐

评论

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