logo AlgoBeat OnlineJudge
登录 注册

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

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。


在二维平面上有 个不同的点。对于每个 ,第 个点的坐标为

等腰三角形是指三条边中有两条边长度相等的三角形。直角三角形是指一个内角为直角 () 的三角形。直角三角形的斜边是指直角三角形中与直角相对的边,也是长度最长的边。等腰直角三角形是指既是直角三角形又是等腰三角形的三角形。即,三角形的一个内角为直角,且除斜边外的两条直角边长度相等的三角形。

请编写一个程序,找出满足以下两个条件的所有等腰直角三角形中,斜边长度最短的那个,并输出其斜边长度。

  • 个点 都位于等腰直角三角形的边界(边上)或其内部。如果某个点位于等腰直角三角形的顶点上,也视为位于边界上。
  • 斜边与 轴平行。也就是说,等腰直角三角形斜边的两个端点的 坐标相同。这意味着只有如下图所示的两种等腰直角三角形满足条件:直角顶点在斜边上方的,和直角顶点在斜边下方的。

例如,假设给定如下图所示的 5 个点:。点本身没有大小,但在图中为了方便观察,用圆形表示。

在直角顶点位于斜边上方的等腰直角三角形中,斜边最短的是如下图所示的,三个顶点为 的三角形,这个等腰直角三角形的斜边长度为 11。

在直角顶点位于斜边下方的等腰直角三角形中,斜边最短的是如下图所示的,三个顶点为 的三角形,这个等腰直角三角形的斜边长度为 14。

在这两种等腰直角三角形中,斜边较短的是直角顶点位于斜边上方的情况,因此所求的长度为 11。

输入格式

第一行给定一个整数

接下来的 行中,第 () 行给定两个整数 ,以空格分隔。

输出格式

在第一行输出满足所有条件的等腰直角三角形中,斜边长度最短的那个的斜边长度。可以证明答案总是一个整数。

样例

样例输入 1

3
0 0
2 3
4 0

样例输出 1

6

样例输入 2

2
0 0
5 2

样例输出 2

7

样例输入 3

4
1 5
3 2
6 6
7 4

样例输出 3

10

数据范围与提示

样例 1 解释

为三个顶点的等腰直角三角形满足所有条件,其斜边长度为 6,是最短的。

样例 2 解释

满足所有条件且斜边长度为 7 的等腰直角三角形有如下两种。

  • 为三个顶点的三角形

  • 为三个顶点的三角形

限制条件

  • 给定的所有数都是整数。
  • 对于每个 ,有
  • 给定的 个点都各不相同。也就是说,对于所有 ,都有

子任务

  1. (10 分)
  2. (18 分)
  3. (20 分) ,且对于每个 ,有
  4. (10 分)
  5. (4 分) 对于每个 ,有 。也就是说,所有点的 坐标都相同。
  6. (6 分) 对于每个 ,有
  7. (10 分) 在所有满足给定条件且斜边长度最短的等腰直角三角形中,至少有一个的斜边中点是
  8. (22 分) 无附加限制条件。