The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——K. Kitten Greetings

题目大意

题目描述

给定二维平面上的 $N$ 只猫的坐标，保证没有任何两只猫的 $X$ 坐标相同，也没有任何两只猫的 $Y$ 坐标相同。

你需要设计一条符合以下规则的回路（包含 $m$ 个步骤，问候 $m$ 只不同的猫）：

1. 选择一个起点 $(x_0, y_0)$，并面向四个基本方向（东、南、西、北）之一。

2. 在第 $i$ 步（$1 \le i \le m$）中：

• 选择一个距离 $k_i > 0$，沿着当前方向直线前进 $k_i$ 的距离，此时必须恰好停在一只之前从未问候过的猫的位置。
• 问候这只猫。
• 不改变方向，继续直线前进 $k_i$ 的距离，到达点 $(x_i, y_i)$。
• 左转或右转 90 度，面向一个新的基本方向。

1. 完成所有 $m$ 步后，必须回到起点 $(x_0, y_0)$，并且面向初始方向。

整条路线的总长度为 $\sum_{i=1}^{m} 2k_i$。如果 $m=0$，则路线长度为 $0$。
请计算并输出符合上述规则的路线的最大总长度。

（注：由于猫的 $X$ 和 $Y$ 坐标互不相同，平面上任意水平或垂直的直线上最多只有一只猫。因此题目等价于：在平面上寻找一个边平行于坐标轴且边数偶数的闭合多边形，该多边形的每一条边的中点都恰好是一只猫，求该多边形的最大周长。）

输入格式

第一行包含一个整数 $N$（$1 \le N \le 4000$），表示猫的数量。
接下来 $N$ 行，每行包含两个整数 $X$ 和 $Y$（$-10^8 \le X, Y \le 10^8$），表示一只猫的坐标。
保证没有任何两只猫的 $X$ 坐标相同，也没有任何两只猫的 $Y$ 坐标相同。

输出格式

输出一个整数，表示符合条件的路线的最大总长度。

样例 1

输入

5
1 2
2 1
0 0
-1 -2
-2 -1

输出

0

样例 1 解释
虽然存在一条长度为 16 且经过所有猫的回路，但它不符合规则，因为沿途位于 $(0,0)$ 的猫会被问候两次，而题目要求每次经过的猫都必须是之前未曾问候过的。

样例 2

输入

6
4 0
0 4
2 -1
-1 2
-4 3
3 -4

输出

32

样例 2 解释
存在一条长度为 32 的路线，可以完美经过并问候所有 6 只猫。每只猫都恰好位于路线某条直线段的正中点。

样例 3

输入

7
2 1
0 -1
5 5
3 0
4 4
6 2
1 -2

输出

24

样例 3 解释
在给定的 $N=7$ 只猫中，可以选择其中的 $m=6$ 只猫构成一条合法的路线，其能达到的最大长度为 24。

思路讲解

这个数据是 $O(n^2)$ 的。

AC代码

源代码

心路历程（WA，TLE，MLE……）