P16557 [ICPC 2026 LAC] Kitten Greetings
题目描述
Catarina 喜爱她社区中的所有猫。她的毕生梦想是设计一条大型的**观猫路线**，这样她每天都可以出门散步，同时向猫咪们打招呼。Catarina 的社区可以表示为二维平面，南北方向与 $y$ 轴对齐。一条拜访了 $m$ 只猫的观猫路线恰好包含 $m$ 步。Catarina 选择一个起始位置 $(x_0, y_0)$，并面向四个基本方向之一。对于每一步 $i = 1, 2, \ldots, m$，发生以下事件：
- Catarina 选择一个正数 $k_i > 0$，从 $(x_{i-1}, y_{i-1})$ 沿当前方向直走 $k_i$ 个单位，停在一只猫所在的位置，且该猫在之前的任何步骤中都未被问候过。
- Catarina 向这只猫打招呼，花一些时间欣赏它的美丽。
- 在不转向的情况下，Catarina 再沿当前方向直走 $k_i$ 个单位，停在位置 $(x_i, y_i)$。
- Catarina 顺时针或逆时针旋转 $90^\circ$，再次面向四个基本方向之一。
完成所有 $m$ 步后，Catarina 必须回到她的起始位置 $(x_0, y_0)$，并且面向初始方向。注意观猫路线的总长度为 $\sum_{i=1}^m 2k_i$。当 $m = 0$ 时，观猫路线的长度为 $0$。
Catarina 知道她社区中 $N$ 只猫的位置。令人惊讶的是，没有两只猫具有相同的 $x$ 坐标或相同的 $y$ 坐标。你的任务是确定一条观猫路线可能达到的最大长度。
输入格式
第一行包含一个整数 $N$（$1 \le N \le 4000$），表示猫的数量。
接下来 $N$ 行，每行描述一只猫，包含两个整数 $X$ 和 $Y$（$-10^8 \le X, Y \le 10^8$），表示该猫的坐标为 $(X, Y)$。
没有两只猫具有相同的 $x$ 坐标或相同的 $y$ 坐标（它们在两个坐标上都不同）。
输出格式
输出一行一个整数，表示一条观猫路线可能达到的最大长度。
说明/提示
**样例 1 解释：**
在此情况下，存在一条长度为 $16$ 且拜访了所有猫的回路，但它不是观猫路线，因为坐标为 $(0, 0)$ 的猫被问候了两次。
**样例 2 解释：**
下图用小圆圈显示了猫的位置，以及一条拜访了所有猫且长度最大的观猫路线。该路线的长度为 $32$。
:::align{center}
:::
**样例 3 解释：**
可以用一条长度为 $24$ 的观猫路线拜访 $N = 7$ 只猫中的 $m = 6$ 只。
:::align{center}
:::
翻译由 DeepSeek V4 Pro 完成