#P18496. 2D Parentheses
2D Parentheses
2D Parentheses
二维平面上有 个左括号和 个右括号。第 个左括号坐标为 ,第 个右括号坐标为 。
你要进行以下操作 次,在平面上放置矩形:
- 选择一个左括号和一个右括号。若它们的坐标分别为 和 ,则必须满足 且 。
- 从平面移去这两个括号,放置一个四个顶点依次为 、、、 的矩形。
判断能否放置 个矩形,使任意两个不同矩形满足:它们的公共面积为 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}
- 所有输入值均为整数;
- ;
- ,其中 ,;
- 若 ,则 。
也就是说,全部 个点互不相同,但不同点可以有相同横坐标或相同纵坐标。本题为单组输入。
输出格式
如果无解,输出一行 No。
否则,第一行输出 Yes。接下来对 ,依次输出左括号 所配对的右括号下标 。每个右括号必须恰好使用一次。
若有多种合法方案,可以输出任意一种。
样例 1
3
0 0
2 -2
1 1
2 2
3 1
2 3
Yes
3
2
1
按图放置矩形即可满足要求。圆点表示左括号,叉号表示右括号。

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


样例 3
1
1 1
0 0
No
无法放置满足严格坐标条件的矩形。
