P13741 [NWERC 2024] Connect Five
题目描述
在 Nattanham 镇，所有的道路要么南北走向，要么东西走向，并且贯穿整个小镇。此外，所有道路之间的间距相等。这使得在镇上导航非常容易。
不幸的是，道路状况很差，需要重新铺设沥青。然而，资金有限，无法修复所有道路，因此部分路段需要优先维修。
市长选定了镇上五个非常重要的位置：市政厅、警察局、医院、消防局，以及市长的住宅。这些位置都位于道路交叉口。
市长希望，对于这五个重要位置中的每一对，都能够通过一条全程由翻新道路组成的最短路径相互到达。在此限制下，市长希望翻新道路的总长度最小。交叉口不计入翻新长度。下图展示了一种最优的翻新道路配置。
:::align{center}
图 C.1：样例输入 1 的示意图，重要位置用首字母标记，并给出了一种翻新最少路段（$22$ 段）的方案。点 $(0,0)$ 位于网格的左下角。
:::
输入格式
输入包含五行，每行两个整数 $x$ 和 $y$（$0 \le x, y \le 1000$），表示五个重要位置在网格上的坐标。
保证所有位置互不相同。
输出格式
输出需要翻新的最少道路段数。
说明/提示
由 ChatGPT 4.1 翻译