#P18358. Guarding Plan
Guarding Plan
Guarding Plan
题目描述
二维坐标平面上有 名警卫,第 名警卫位于点 。最初任意两名警卫的位置不同。
你可以进行任意次以下操作,也可以不进行操作:
选择两个当前有警卫站立的点,再选择这两个点之间线段上的任意一点。如果所选位置目前没有警卫,就在那里增加一名警卫。
新警卫的位置不要求是整数坐标。原有警卫不会因操作而消失。
位于 的警卫能够监视所有满足 且 的位置上的警卫。如果一名警卫没有被任何其他警卫监视,就称其为必要警卫。
请先使最终配置中的必要警卫数量尽可能少;在达到这个最少数量的所有操作方案中,再使操作次数尽可能少。求这两个最小值。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示一名警卫的位置。
输出格式
第一行输出最终必要警卫数量的最小值。
第二行输出在达到上述最小值的前提下,所需操作次数的最小值。
数据范围
- 输入中的数值均为整数。
- 。
- 。
- 当 时,。
- 每个输入文件只有一组数据。
样例输入 1
5
1 6
2 4
3 3
4 2
6 1
样例输出 1
4
1
样例输入 2
3
0 0
1 2
2 1
样例输出 2
2
0
样例输入 3
7
10 49
9 27
59 8
19 22
0 50
25 23
33 13
样例输出 3
4
1
样例解释
在样例 1 中,点 位于 与 之间的线段上。在 增加一名警卫后,必要警卫恰好位于 、、、,因此答案为 和 。