## Problem G. Geometric similarity ≡

• problems
• en ru
 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

### Statement

There are two simple (without self-intersections) polygons, each represented by a sequence of vertices in either clockwise or counter-clockwise order.

Your program must determine whether the polygons are similar, that is, whether one of them can be transformed into another by applying zero or more of the following operations:

• scaling all edges by a non-zero constant;
• rotating by 90 in any direction around some fixed point;
• translation (offset by a vector);
• orientation changing (from clockwise to counter-clockwise and vice-versa).
The choice of initial vertex might also be different.

### Input format

Input contains integer n, followed by 2 ⋅ n vertices (first one polygon, then another), represented by pairs of integers: (xi, yi).

### Output format

Output must contain a single integer: 1, if polygons are similar, 0 otherwise.

### Constraints

It is guaranteed that both polygons are non-degenerate, i.e. have an area strictly greater than zero.

All edges also have non-zero length.

− 104 ≤ (xi, yi) ≤ 104, 3 ≤ n ≤ 105

### Sample tests

No. Standard input Standard output
1
5
-300 300
-100 500
200 400
200 200
-100 100

250 120
150 220
50 120
100 -30
200 -30

1
2
5
100 200
0 400
300 300
300 100
0   0

350 150
150 320
50 220
100   0
200   0

0

0.069s 0.008s 13