#P11758. [COTS 2014] 餐厅建设 / KOSTA
[COTS 2014] 餐厅建设 / KOSTA
题目描述
烧烤大师 Kosta 在曼哈顿开了 家餐厅,按照 到 的数字进行标记,每个餐厅的位置都可以按照坐标轴上的点进行表示,比如餐厅 标记为 。同时两个餐厅 的距离为。
Kosta 计划最多购买两台用于自动制作汉堡的现代化机器。每台机器都将安装在现有的餐厅中,对于所有其他餐厅,汉堡都是从安装机器的最近餐厅送来的。
我们定义 表示从餐厅 到安装机器的餐厅的最小距离。Kosta 希望 的最大值最小。
编写一个程序,根据餐厅的位置和 Kosta 将购买的机器数量(一台或两台),计算 的最低可能值。此外,你应确定机器的最佳位置。如果 Kosta 购买了两台机器,可以在同一家餐厅安装两台机器。
输入格式
第一行为一个整数 ,表示购买机器的数量。
第二行为一个整数 ,表示餐厅的数量。在接下来的 行中,每行给出 表示餐厅坐标 ,餐厅的坐标互不相同。
输出格式
在第一行中,一个整数 。
在第二行中,输出 个自然数,表示要装电器的餐厅。
注意:解决方案不必是唯一的。
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
提示
若 正确,但是第二行答案错误,你可以获得 的分数。
- Subtask ( pts): 。
- Subtask ( pts):。
- Subtask ( pts): 。
- Subtask ( pts):。
- Subtask ( pts):。