P11758 [COTS 2014] 餐厅建设 / KOSTA

烧烤大师 Kosta 在曼哈顿开了 $N$ 家餐厅，按照 $1$ 到 $N$ 的数字进行标记，每个餐厅的位置都可以按照坐标轴上的点进行表示，比如餐厅 $A$ 标记为 $(X_A,Y_A)$。同时两个餐厅 $A,B$ 的距离为$|X_A-X_B|+|Y_A-Y_B|$。 Kosta 计划最多购买**两台**用于自动制作汉堡的现代化机器。每台机器都将安装在现有的餐厅中，对于所有其他餐厅，汉堡都是从安装机器的最近餐厅送来的。 我们定义 $D_C$ 表示从餐厅 $C$ 到安装机器的餐厅的最小距离。Kosta 希望 $D_C$ 的最大值最小。 编写一个程序，根据餐厅的位置和 Kosta 将购买的机器数量（一台或两台），计算 $D_C$ 的最低可能值。此外，你应确定机器的最佳位置。如果 Kosta 购买了两台机器，可以在同一家餐厅安装两台机器。

第一行为一个整数 $K(1\le K\le 2)$，表示购买机器的数量。 第二行为一个整数 $N$，表示餐厅的数量。在接下来的 $N$ 行中，每行给出 $(X_K,Y_K)$ 表示餐厅坐标 $(0\le X_K,Y_K \le 10^6)$，餐厅的坐标互不相同。

在第一行中，一个整数 $D$。 在第二行中，输出 $K$ 个自然数，表示要装电器的餐厅。 注意：解决方案不必是唯一的。

若 $D$ 正确，但是第二行答案错误，你可以获得 $60 \%$ 的分数。 - Subtask $1$（$4$ pts）： $K=1,1\le N\le 1000$。 - Subtask $2$（$16$ pts）：$K=1,1000< N\le 200000$。 - Subtask $3$（$4$ pts）： $K=2,3\le N\le 100$。 - Subtask $4$（$24$ pts）：$K=2,100\le N\le 3000$。 - Subtask $5$（$52$ pts）：$K=2,3000< N\le 50000$。