#P17755. 警备员
警备员
题目描述
二维坐标平面上有 名警备员。第 名警备员站在点 。你可以将下面的操作执行 次以上任意多次。
- 从当前有警备员站立的点中选择 个点,并选择以这两个点为端点的线段上的 个点。如果这个点上还没有警备员,则在这个点上新安排一名警备员。
站在点 的警备员,会监视所有满足 坐标不超过 且 坐标不超过 的区域内的警备员。警备员也会监视自己。
没有被自己以外的任何警备员监视的警备员,称为「必要的警备员」。
请你求出,最终的警备员配置中,「必要的警备员」人数的最小值。进一步地,在达到这个最小值的所有方案中,求所需操作次数的最小值。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示第 名警备员的位置。
输出格式
输出 行。
第 行输出最终可以达到的「必要的警备员」人数的最小值。
第 行输出在达到上述最小值的前提下,所需操作次数的最小值。
样例 1
5
1 6
2 4
3 3
4 2
6 1
4
1
样例 2
3
0 0
1 2
2 1
2
0
样例 3
7
10 49
9 27
59 8
19 22
0 50
25 23
33 13
4
1
样例 4
见下发文件。
样例 5
见下发文件。
数据范围与约定
对于所有测试数据,满足 ;;()。
对于 的测试数据,,。
对于 的测试数据,,。
对于 的测试数据,。
对于 的测试数据,。
对于 的测试数据,无额外限制。