#P11758. [COTS 2014] 餐厅建设 / KOSTA

    ID: 13131 远端评测题 5000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2014Special JudgeCOCI(克罗地亚)

[COTS 2014] 餐厅建设 / KOSTA

题目描述

烧烤大师 Kosta 在曼哈顿开了 NN 家餐厅,按照 11NN 的数字进行标记,每个餐厅的位置都可以按照坐标轴上的点进行表示,比如餐厅 AA 标记为 (XA,YA)(X_A,Y_A)。同时两个餐厅 A,BA,B 的距离为XAXB+YAYB|X_A-X_B|+|Y_A-Y_B|

Kosta 计划最多购买两台用于自动制作汉堡的现代化机器。每台机器都将安装在现有的餐厅中,对于所有其他餐厅,汉堡都是从安装机器的最近餐厅送来的。

我们定义 DCD_C 表示从餐厅 CC 到安装机器的餐厅的最小距离。Kosta 希望 DCD_C 的最大值最小。

编写一个程序,根据餐厅的位置和 Kosta 将购买的机器数量(一台或两台),计算 DCD_C 的最低可能值。此外,你应确定机器的最佳位置。如果 Kosta 购买了两台机器,可以在同一家餐厅安装两台机器。

输入格式

第一行为一个整数 K(1K2)K(1\le K\le 2),表示购买机器的数量。

第二行为一个整数 NN,表示餐厅的数量。在接下来的 NN 行中,每行给出 (XK,YK)(X_K,Y_K) 表示餐厅坐标 (0XK,YK106)(0\le X_K,Y_K \le 10^6),餐厅的坐标互不相同。

输出格式

在第一行中,一个整数 DD

在第二行中,输出 KK 个自然数,表示要装电器的餐厅。

注意:解决方案不必是唯一的。

2
5
1 1
2 3
5 10
4 6
7 12
5
1 3 
2
10
3 6
1 4
4 1
4 7
4 10
3 8
3 10
6 7
5 1
2 10
5
1 3 
1
10
3 10
6 1
5 7
0 4
2 7
2 0
9 2
4 1
3 6
1 4
10
3

提示

DD 正确,但是第二行答案错误,你可以获得 60%60 \% 的分数。

  • Subtask 1144 pts): K=1,1N1000K=1,1\le N\le 1000
  • Subtask 221616 pts):K=1,1000<N200000K=1,1000< N\le 200000
  • Subtask 3344 pts): K=2,3N100K=2,3\le N\le 100
  • Subtask 442424 pts):K=2,100N3000K=2,100\le N\le 3000
  • Subtask 555252 pts):K=2,3000<N50000K=2,3000< N\le 50000