← 返回题目列表

AtCoder · ttpc2023_o

O. 2D 括号

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

配点 : 100 点

問題文

2 左括号和右括号分别位于维度平面上。 有 N 件。 第 i 个左括号的坐标是 第 (x_{1, i}, y_{1, i}) 、 i 个右括号的坐标是 (x_{2, i}, y_{2, i}) 。

x_{1, i} < x_{2, j} 和 满足 y_{1, i} < y_{2, j} 当且仅当 i 带左括号 从平面上删除第 j 个右括号并将其替换为 以 4 点 (x_{1, i}, y_{1, i}), (x_{1, i}, y_{2, j}), (x_{2, j}, y_{2, j}), (x_{2, j}, y_{1, i}) 为顶点的矩形可以放置在平面上。

任何不同 2 两个矩形的公共部分的面积为 0 或匹配矩形之一。 确定是否可以在平面中排列 N 矩形,如果可能,请确定如何这样做。 1 请找到一个。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq x_{p, i}, y_{p, i} \leq 10^9
  • (p, i) \neq (q, j) 如果 (x_{p, i}, y_{p, i}) \neq (x_{q, j}, y_{q, j})
  • 所有输入均为整数 如果有办法做到

入力

输入是按以下格式从标准输入给出的。

N
x_{1, 1} y_{1, 1}
x_{1, 2} y_{1, 2}
\vdots
x_{1, N} y_{1, N}
x_{2, 1} y_{2, 1}
x_{2, 2} y_{2, 2}
\vdots
x_{2, N} y_{2, N}

出力

如果没有满足条件的展示位置, 在一行上输出No 。

如果有满足条件的展示位置,首先 在一行上输出 Yes 。那么按照这样的安排 在 i 番目 (1 \le i \le N) 的左括号中 假设 c_i 番目 (1 \le c_i \le N) 的右括号对应, 在 i 行 c_i 。

如果有多个位置满足条件,则其中任何一个都是正确答案。


入力例 1

3
0 0
2 -2
1 1
2 2
3 1
2 3

出力例 1

Yes
3
2
1

放置如下所示的矩形即可满足条件。

在图中,圆圈代表左括号,十字标记代表右括号。


入力例 2

2
1 0
0 1
2 3
3 2

出力例 2

No

如图所示,无论你如何排列矩形,都无法满足条件。


入力例 3

1
1 1
0 0

出力例 3

No

不幸的是,不可能首先放置一个矩形。