#P17755. 警备员

警备员

题目描述

二维坐标平面上有 NN 名警备员。第 ii 名警备员站在点 (xi,yi)(x_i,y_i)。你可以将下面的操作执行 00 次以上任意多次。

  • 从当前有警备员站立的点中选择 22 个点,并选择以这两个点为端点的线段上的 11 个点。如果这个点上还没有警备员,则在这个点上新安排一名警备员。

站在点 (a,b)(a,b) 的警备员,会监视所有满足 xx 坐标不超过 aa 且 yy 坐标不超过 bb 的区域内的警备员。警备员也会监视自己。

没有被自己以外的任何警备员监视的警备员,称为「必要的警备员」。

请你求出,最终的警备员配置中,「必要的警备员」人数的最小值。进一步地,在达到这个最小值的所有方案中,求所需操作次数的最小值。

输入格式

第一行一个整数 NN。

接下来 NN 行,每行两个整数 xi,yix_i,y_i,表示第 ii 名警备员的位置。

输出格式

输出 22 行。

第 11 行输出最终可以达到的「必要的警备员」人数的最小值。

第 22 行输出在达到上述最小值的前提下,所需操作次数的最小值。

样例 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

见下发文件。

数据范围与约定

对于所有测试数据,满足 1≤N≤2×1051\le N\le 2\times 10^5;0≤xi,yi≤1090\le x_i,y_i\le 10^9;(xi,yi)≠(xj,yj)(x_i,y_i)\ne (x_j,y_j)(i≠ji\ne j)。

对于 20%20\% 的测试数据,N≤10N\le 10,0≤xi,yi≤200\le x_i,y_i\le 20。

对于 40%40\% 的测试数据,N≤200N\le 200,0≤xi,yi≤1040\le x_i,y_i\le 10^4。

对于 60%60\% 的测试数据,N≤5000N\le 5000。

对于 80%80\% 的测试数据,N≤50000N\le 50000。

对于 100%100\% 的测试数据,无额外限制。