Chino's Latte Art

Time limit1sMemory limit1024 MB

Summary

Given a simple polygon, decide whether one reflex vertex and one convex vertex form a symmetry axis that splits it into two convex halves.

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

Problem

Chino practices making heart-shaped latte art. Cocoa comes across the traces of Chino's many practice attempts and wants to know how many of the latte arts are heart-shaped. Write a program that decides whether a latte art is heart-shaped, for Cocoa.

In this problem, Chino's latte art is a simple polygon.

A polygon is heart-shaped if there exist vertices $A$ and $B$ of the polygon such that all of the following conditions hold.

The interior angle at $A$ is less than $180$ degrees, and the interior angle at $B$ is greater than $180$ degrees.
The given polygon is symmetric about the line $AB$ .
The two parts formed when the given polygon is cut along the segment $AB$ are both convex polygons.

Input

The first line contains the number of vertices $N$ of the polygon. ( $3 \le N \le 100\,000$ )

Each of the next $N$ lines contains the $x$ coordinate and the $y$ coordinate of a vertex, separated by a space. ( $-10^9 \le x,y \le 10^9$ , $x$ , $y$ are integers)

The vertices are given clockwise, starting from an arbitrary point.

No vertex of the given polygon has an interior angle of exactly $180$ degrees.

Output

If the given polygon is heart-shaped, print 1. Otherwise, print 0.

Examples2

Example 1
Input
```
6
0 0
0 5
3 5
3 3
5 3
5 0
```
Expected output
```
1
```

Example 2

Input

Expected output