Football Fields

Interview

Time limit2sMemory limit1024 MB

Summary

Given two convex polygons, decide whether one can be mapped onto the other using translations and the eight symmetries generated by axis and diagonal reflections.

Level: Medium6 of 10
Topics: String matching, Geometry
Solved: No attempts yet

Problem

Flatland is a country where people love football. Ordinary rectangular fields have long bored everyone, so Flatlanders invented a game played on fields of arbitrary shape. Each field is a convex polygon. Under the rules of the Flatland Football Association, every stadium must have its own unique shape, unlike the shape of any other stadium.

Two polygons are given, each describing one field. The vertices of each polygon are listed in clockwise or counterclockwise order, starting from an arbitrary vertex. The two polygons may be listed in different orders. Determine whether the two fields are identical. Two fields are identical if one can be obtained from the other by a sequence of translations, reflections across any horizontal or vertical line, and reflections across the lines $y = x$ or $y = -x$ .

Input

The first line contains an integer $n$ ( $3 \le n \le 10^5$ ), the number of vertices in a polygon. Each of the next $n$ lines contains two integers $x$ and $y$ ( $-10^9 \le x, y \le 10^9$ ), the coordinates of a vertex of the first polygon.

The next $n$ lines describe the vertices of the second polygon in the same format.

Both polygons are convex. No three consecutive vertices of one polygon lie on a single line. The vertices of each polygon are listed in clockwise or counterclockwise order, starting from an arbitrary vertex. The two polygons may be listed in different traversal orders.

Output

Print YES if the two fields are identical, and NO otherwise.

Examples1

Example 1
Input
```
3
0 0
1 1
1 0
2 2
3 2
3 1
```
Expected output
```
YES
```