D - Congruence Points Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

要素数が共に N であるような二次元平面上の点の集合 S=\{(a_1,b_1),(a_2,b_2),\ldots,(a_N,b_N)\} と T=\{(c_1,d_1),(c_2,d_2),\ldots,(c_N,d_N)\} が与えられます。

S に対して以下の操作を 0 回以上任意の順に好きなだけ繰り返すことで、S と T を一致させられるかを判定してください。

  • 実数 p\ (0 \lt p \lt 360) を定め、 S に含まれる全ての点を、原点を中心に時計回りに p 度回転させる。
  • 実数 q,r を定める。S に含まれる全ての点を、x 軸方向に q, y 軸方向に r 移動させる。q, r の値域に制約はなく、特に正/負/零のいずれになってもよい。

制約

  • 1 \leq N \leq 100
  • -10 \leq a_i,b_i,c_i,d_i \leq 10
  • i \neq j なら (a_i,b_i) \neq (a_j,b_j)
  • i \neq j なら (c_i,d_i) \neq (c_j,d_j)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
\hspace{0.6cm}\vdots
a_N b_N
c_1 d_1
c_2 d_2
\hspace{0.6cm}\vdots
c_N d_N

出力

問題文中の操作によって S と T を一致させられるなら Yes を、一致させられないなら No を出力せよ。

入力例 1

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

出力例 1

Yes

S に含まれる点を赤で、T に含まれる点を緑で塗った場合、与えられる点集合は以下の図の通りになります。

この場合、以下の手順によって S を T に一致させることができます。

  1. S に含まれる全ての点を、原点を中心に時計回りに 270 度回転させる。
  2. S に含まれる全ての点を、x 軸方向に 3, y 軸方向に 0 移動させる。

入力例 2

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

出力例 2

No

入力に対応する図は以下の通りです。

S と T は y 軸に対して線対称ですが、問題文中に書かれているような回転操作、移動操作によって S と T を一致させることはできません。

入力例 3

4
0 0
2 9
10 -2
-6 -7
0 0
2 9
10 -2
-6 -7

出力例 3

Yes

入力例 4

6
10 5
-9 3
1 -5
-6 -5
6 9
-9 0
-7 -10
-10 -5
5 4
9 0
0 -10
-10 -2

出力例 4

Yes

Score : 400 points

Problem Statement

You are given two sets S=\{(a_1,b_1),(a_2,b_2),\ldots,(a_N,b_N)\} and T=\{(c_1,d_1),(c_2,d_2),\ldots,(c_N,d_N)\} of N points each on a two-dimensional plane.

Determine whether it is possible to do the following operations on S any number of times (possibly zero) in any order so that S matches T.

  • Choose a real number p\ (0 \lt p \lt 360) and rotate every point in S p degrees clockwise about the origin.
  • Choose real numbers q and r and move every point in S by q in the x-direction and by r in the y-direction. Here, q and r can be any real numbers, be it positive, negative, or zero.

Constraints

  • 1 \leq N \leq 100
  • -10 \leq a_i,b_i,c_i,d_i \leq 10
  • (a_i,b_i) \neq (a_j,b_j) if i \neq j.
  • (c_i,d_i) \neq (c_j,d_j) if i \neq j.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\hspace{0.6cm}\vdots
a_N b_N
c_1 d_1
c_2 d_2
\hspace{0.6cm}\vdots
c_N d_N

Output

If we can match S with T, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

The figure below shows the given sets of points, where the points in S and T are painted red and green, respectively:

In this case, we can match S with T as follows:

  1. Rotate every point in S 270 degrees clockwise about the origin.
  2. Move every point in S by 3 in the x-direction and by 0 in the y-direction.

Sample Input 2

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

Sample Output 2

No

The figure below shows the given sets of points:

Although S and T are symmetric about the y-axis, we cannot match S with T by rotations and translations as stated in Problem Statement.

Sample Input 3

4
0 0
2 9
10 -2
-6 -7
0 0
2 9
10 -2
-6 -7

Sample Output 3

Yes

Sample Input 4

6
10 5
-9 3
1 -5
-6 -5
6 9
-9 0
-7 -10
-10 -5
5 4
9 0
0 -10
-10 -2

Sample Output 4

Yes