← 返回题目列表

AtCoder · utpc2024_g

G. 守护计划

中文机器翻译题面 查看原题

配点 : 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