【codechef】【May Challenge 2019 Division 2】【Where to Build the Roads】题解

[题目链接](https://www.codechef.com/MAY19B/problems/WTBTR) ### 题目描述 大厨买了个很大很大（可以视作无穷大）的岛，在岛上建了 $N$ 座餐馆，编号为 $1 \sim N$ 第 $i$ 座餐馆的坐标为 $(X_i, Y_i)$ 大厨计划在岛上建造 $N-1$ 条道路（可以视作线段） 道路可以任意长，餐馆也不需要在道路上 每条道路的斜率必须为 $1$ 或者 $-1$，也即，如果两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 位于同一条道路上，那 么其坐标必须满足 $|x_1-x_2|=|y_1-y_2|$ 记大厨从餐馆 $i$ 走到任意道路上的最短距离为 $D_i$ 大厨想要最小化 $a = \max(D_1, D_2, \cdots , D_N )$ 大厨是个大忙人，所以他决定把规划道路的任务交给你 你需要求出使得 $a$ 达到最小的方案，并输出 $\sqrt{2}a$ 的值 其中 $2 \le N \le 10^4, 1 \le T \le 100, |X_i|,|Y_i| \le 10^9$ ### 题解 也就是用 $n-1$ 条斜率为 $\pm 1$ 的直线去搞 那么就尽可能多的把直线直接丢到点上 然而这样会少一条直线，不妨枚举一个点 $p_1$，然后再枚举一个点 $p_2$，用一条在 $p_1,p_2$ 的中点处的直线去搞上去 运用高中所学的点到直线距离公式以及中点公式，可以得到要最小化： $$\min \left(\frac{1}{2\sqrt{2}} \Big|(y_1-x_1)-(y_2-x_2)\Big|\right)$$ 在此只考虑斜率为 $1$ 的情况，如果是 $-1$，只需要把所有点的 $x$ 坐标变成 $-x$，然后再跑一遍就行了 不妨直接把每个点按照 $y_1-x_1$ 排序，那么最优解一定是相邻两项中的某一个