Problem G. Geometric similarity

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:

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.077s 0.009s 13