#P18496. 2D Parentheses

2D Parentheses

2D Parentheses

二维平面上有 NN 个左括号和 NN 个右括号。第 ii 个左括号坐标为 (x1,i,y1,i)(x_{1,i},y_{1,i}),第 ii 个右括号坐标为 (x2,i,y2,i)(x_{2,i},y_{2,i})。

你要进行以下操作 NN 次,在平面上放置矩形:

  • 选择一个左括号和一个右括号。若它们的坐标分别为 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2),则必须满足 x1<x2x_1<x_2 且 y1<y2y_1<y_2。
  • 从平面移去这两个括号,放置一个四个顶点依次为 (x1,y1)(x_1,y_1)、(x1,y2)(x_1,y_2)、(x2,y2)(x_2,y_2)、(x2,y1)(x_2,y_1) 的矩形。

判断能否放置 NN 个矩形,使任意两个不同矩形满足:它们的公共面积为 0,或者其中一个完全包含于另一个。 如果能,给出一种放置方案。

公共面积为 0 允许仅边界相接;包含关系允许边界重合。配对矩形本身必须满足上述两个严格不等式,不能有零宽或零高。

输入格式

N
x_{1,1} y_{1,1}
...
x_{1,N} y_{1,N}
x_{2,1} y_{2,1}
...
x_{2,N} y_{2,N}
  • 所有输入值均为整数;
  • 1≤N≤2×1051\le N\le2\times10^5;
  • −109≤xp,i,yp,i≤109-10^9\le x_{p,i},y_{p,i}\le10^9,其中 p∈{1,2}p\in\{1,2\},1≤i≤N1\le i\le N;
  • 若 (p,i)≠(q,j)(p,i)\ne(q,j),则 (xp,i,yp,i)≠(xq,j,yq,j)(x_{p,i},y_{p,i})\ne(x_{q,j},y_{q,j})。

也就是说,全部 2N2N 个点互不相同,但不同点可以有相同横坐标或相同纵坐标。本题为单组输入。

输出格式

如果无解,输出一行 No。

否则,第一行输出 Yes。接下来对 i=1,2,…,Ni=1,2,\ldots,N,依次输出左括号 ii 所配对的右括号下标 cic_i。每个右括号必须恰好使用一次。 若有多种合法方案,可以输出任意一种。

样例 1

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

按图放置矩形即可满足要求。圆点表示左括号,叉号表示右括号。

原样例1:含套和边接触

样例 2

2
1 0
0 1
2 3
3 2
No

无论怎样配对都无法满足条件。两种配对分别如下,它们均存在公共面积为正且不互相包含的两个矩形。

原样例2第一种配对

原样例2第二种配对

样例 3

1
1 1
0 0
No

无法放置满足严格坐标条件的矩形。

原样例3:不能形成矩形