专栏文章

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

cchen_zheAya
P13511题解参与者 12已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@miontkh6
此快照首次捕获于
2025/12/02 22:14
3 个月前
此快照最后确认于
2025/12/02 22:14
3 个月前
查看原文

子问题 3

作为答案的直角等腰三角形，可以分为其直角顶点位于斜边上方和下方两种情况。对每种情况分别计算斜边长度的最小值，然后输出两者中较小的值即可。
我们设连接直角等腰三角形斜边的两个端点为 (a,c)(a, c) 和 (b,c)(b, c)。（a<ba < b）由于给定的所有点的 x,yx, y 坐标的绝对值最大为 30，因此不需要考虑 ∣a∣,∣b∣>90,∣c∣>30|a|, |b| > 90, |c| > 30 的三角形。因此，只需对所有满足该条件的直角等腰三角形，检查其是否包含所有给定的点即可。这可以通过多边形内点判断等多种方法实现，但也可以利用以下的观察结论。
设一个直角等腰三角形的斜边端点为 (a,c),(b,c)(a,c), (b,c)（a<ba<b），且其直角顶点位于斜边上方，那么该三角形包含点 (x,y)(x,y) 的条件如下：
  • (x,y)(x,y) 位于斜边或其上方。即，y≥cy \ge c。
  • (x,y)(x,y) 位于经过直角等腰三角形左顶点、斜率为 1 的直线或其下方。即，x−a≥y−cx - a \ge y - c。
  • (x,y)(x,y) 位于经过直角等腰三角形右顶点、斜率为 -1 的直线或其下方。即，−(x−b)≥y−c−(x-b) \ge y - c。
利用上述条件，我们可以在 O(N)O(N) 时间内判断某个直角等腰三角形是否包含所有给定的点。因此，如果输入点的坐标的绝对值最大为 XX，那么总时间复杂度为 O(X3N)O(X^3N)。

子问题 4

可以发现，满足条件且斜边长度最小的直角等腰三角形，其每条边上都至少包含一个给定的点。（可以认为，这也包括了边的端点恰好是给定点之一的情况。）
我们先只考虑直角顶点在斜边上方的情况。如果我们在直角等腰三角形的每条边上各选一个点，就可以确定该三角形的三个顶点。因此，对于选择三个点的 N3N^3 种情况，可以确定一个直角等腰三角形。然后，可以利用子问题 3 的解法，检查该三角形是否包含所有 NN 个点，从而解决问题。直角顶点在斜边下方的情况，可以用同样的方法解决。
总时间复杂度为 O(N4)O(N^4)。此外，还存在多种其他多项式时间复杂度的解法来解决该子问题。

子问题 5

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

子问题 6

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

子问题 7

我们先只考虑直角顶点在斜边上方的情况。
假设作为答案的直角等腰三角形，其斜边的右端点坐标为 (d,0)(d,0)。由于该三角形斜边的中点是 (0,0)(0,0)，因此连接斜边的两个顶点的坐标是 (−d,0)(-d, 0) 和 (d,0)(d, 0)，斜边长度为 2d2d。
如果一个斜边长度为 2d2d 的直角等腰三角形包含了所有给定的点，那么对于所有 d′>dd' > d，一个斜边长度为 2d′2d' 的直角等腰三角形也必然包含所有给定的点。
因为需要求斜边长度的最小值，所以可以通过对 dd 进行二分搜索来求出其最小值。对于一个固定的 dd，以 (−d,0)(-d, 0) 和 (d,0)(d,0) 为（斜边）顶点的直角等腰三角形是否包含所有点，可以使用子问题 3 的解法来判断。
用同样的方法，也可以求出直角顶点在斜边下方情况时斜边长度的最小值。如果两种情况都可行，则输出两个斜边长度中较小的一个；如果只有一种情况可行，则输出该情况下的斜边长度。

子问题 8

我们只考虑直角顶点在斜边上方的情况。在这类三角形中，我们设斜边长度最小的三角形，其斜边的两个端点为 (a,c)(a, c) 和 (b,c)(b, c)。（a<ba < b）
设所有给定点的 yy 坐标的最小值为 mm。根据子问题 3 的条件，所有给定点的 yy 坐标都必须大于或等于 cc。即，m≥cm \ge c。如果 m>cm > c，斜边将不包含 NN 个给定点中的任何一个，这与子问题 4 中的观察相矛盾。因此，我们只需考虑 m=cm = c 的情况。
由于 cc 的值已经确定，我们可以根据子问题 3 的条件求出 aa 的最大值和 bb 的最小值。我们需要最小化斜边长度 b−ab-a，因此上述两个值（bb 的最小值和 aa 的最大值）之差就是答案。
直角顶点在斜边下方的情况，也可以用同样的方法解决。
总时间复杂度为 O(N)O(N)。
CPP
/*
* 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;
}

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...