配点 : 100 点
問題文
2 在二维坐标平面上 N 有 人保安站立。i 第 人保安站在点 (x_i, y_i) 上。你可以将以下操作 0 次或以上任意次数重复。
- 选择警卫站立的点 2 个,并且 2 选择以这些点为端点的线段上的 1 个点。如果这些点上没有警卫,就在这些点新安排警卫站立。
点 (a, b) 站立的警卫x 坐标是 a 以下且 y 坐标是 b 监视位于以下区域的警卫。没有被其他警卫监视的警卫称为“必要的警卫”。
请找到最终警卫配置中“必要的警卫”的最小人数。此外,请找到为了将“必要的警卫”人数最小化所需操作次数的最小值。
制約
- 所有输入均为整数
- 1 \leq N \leq 2\times 10^5
- 0 \leq x_i, y_i \leq 10^9 (1\leq i\leq N)
- (x_i, y_i)\neq (x_j, y_j) (i\neq j)
入力
输入是按以下格式从标准输入给出的。
N x_1 y_1 \vdots x_N y_N
出力
2 按行输出。1 在该行输出可实现的“必要的警卫”的最小人数。2 在这一行输出达到该最小值所需操作次数的最小值。
入力例 1
5 1 6 2 4 3 3 4 2 6 1
出力例 1
4 1
点 (1,6) 和点 (6,1) 警卫之间的点 (3,4) 被选择,在这里新安排一名警卫。此操作之后,“所需警卫”在 (1,6),(3,4),(4,2),(6,1) 上将是 4 名。
入力例 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