#P18358. Guarding Plan

Guarding Plan

Guarding Plan

题目描述

二维坐标平面上有 NN 名警卫,第 ii 名警卫位于点 (xi,yi)(x_i,y_i)。最初任意两名警卫的位置不同。

你可以进行任意次以下操作,也可以不进行操作:

选择两个当前有警卫站立的点,再选择这两个点之间线段上的任意一点。如果所选位置目前没有警卫,就在那里增加一名警卫。

新警卫的位置不要求是整数坐标。原有警卫不会因操作而消失。

位于 (a,b)(a,b) 的警卫能够监视所有满足 x≤ax\le a 且 y≤by\le b 的位置上的警卫。如果一名警卫没有被任何其他警卫监视,就称其为必要警卫。

请先使最终配置中的必要警卫数量尽可能少;在达到这个最少数量的所有操作方案中,再使操作次数尽可能少。求这两个最小值。

输入格式

第一行一个整数 NN。

接下来 NN 行,每行两个整数 xi,yix_i,y_i,表示一名警卫的位置。

输出格式

第一行输出最终必要警卫数量的最小值。

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

数据范围

  • 输入中的数值均为整数。
  • 1≤N≤2×1051\le N\le 2\times 10^5。
  • 0≤xi,yi≤1090\le x_i,y_i\le 10^9。
  • 当 i≠ji\ne j 时,(xi,yi)≠(xj,yj)(x_i,y_i)\ne(x_j,y_j)。
  • 每个输入文件只有一组数据。

样例输入 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 中,点 (3,4)(3,4) 位于 (1,6)(1,6) 与 (6,1)(6,1) 之间的线段上。在 (3,4)(3,4) 增加一名警卫后,必要警卫恰好位于 (1,6)(1,6)、(3,4)(3,4)、(4,2)(4,2)、(6,1)(6,1),因此答案为 44 和 11。