/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
無限に広がる xy 平面を考えます。
平面上の N 個の点からなる 2 つの集合 S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \rbrace および T = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace が与えられます。
下記の 2 つの操作のうち、どちらか一方のみを 0 回または 1 回行うことができます。
- x 軸に平行な直線を 1 本選び、S の各点を選んだ直線に関して対称な位置に移動させる。
- y 軸に平行な直線を 1 本選び、S の各点を選んだ直線に関して対称な位置に移動させる。
S を T に集合として一致させることが可能かどうかを判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- |x_i|, |y_i|, |X_i|, |Y_i| \leq 10^9
- i \neq j \Rightarrow (x_i, y_i) \neq (x_j, y_j)
- i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 \vdots x_N y_N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
S を T に集合として一致させることが可能な場合は Yes を、不可能な場合は No を出力せよ。
入力例 1
3 2 3 0 3 0 1 -1 3 1 1 1 3
出力例 1
Yes
S = \lbrace (0, 1), (0, 3), (2, 3) \rbrace, T = \lbrace (1, 3), (-1, 3), (1, 1) \rbrace です。
y 軸に平行な直線として直線 x = 0.5 を選ぶと、S の各点は (0, 1) \rightarrow (1, 1), (0, 3) \rightarrow (1, 3), (2, 3) \rightarrow (-1, 3) と移動し、S を T に集合として一致させることが可能です。よって、Yes を出力します。
入力例 2
2 1 1 0 0 0 0 -1 -1
出力例 2
No
どのように操作を行っても、 S を T に集合として一致させることができないため No を出力します。
問題文中の 2 つの操作のうち、どちらか一方のみしか行えないことに注意してください。
入力例 3
3 3 1 4 1 5 9 5 9 3 1 4 1
出力例 3
Yes
操作を行わなくても S と T は集合として一致しています。
Score : 6 points
Problem Statement
Consider an infinite xy-plane.
You are given two sets of N points each: S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \rbrace and T = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace.
You may do exactly one of the two operations below zero or one time.
- Choose a line parallel to the x-axis and reflect each point in S over the chosen line.
- Choose a line parallel to the y-axis and reflect each point in S over the chosen line.
Determine whether it is possible to make S equal T as a set.
Constraints
- 1 \leq N \leq 2 \times 10^5
- |x_i|, |y_i|, |X_i|, |Y_i| \leq 10^9
- i \neq j \Rightarrow (x_i, y_i) \neq (x_j, y_j)
- i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 \vdots x_N y_N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
If it is possible to make S equal T as a set, print Yes; otherwise, print No.
Sample Input 1
3 2 3 0 3 0 1 -1 3 1 1 1 3
Sample Output 1
Yes
We have S = \lbrace (0, 1), (0, 3), (2, 3) \rbrace, T = \lbrace (1, 3), (-1, 3), (1, 1) \rbrace.
If you choose the line x = 0.5, which is parallel to the y-axis, each point in S moves as follows: (0, 1) \rightarrow (1, 1), (0, 3) \rightarrow (1, 3), (2, 3) \rightarrow (-1, 3), after which S is equal to T as a set. Thus, Yes should be printed.
Sample Input 2
2 1 1 0 0 0 0 -1 -1
Sample Output 2
No
There is no way to do an operation to make S equal T as a set, so No should be printed.
Note that you may do only one of the two operations in the Problem Statement.
Sample Input 3
3 3 1 4 1 5 9 5 9 3 1 4 1
Sample Output 3
Yes
Before doing any operation, S is already equal to T.