题目描述

Ingrid holds a polygon shop in a far away country. She sells only convex polygons with integer coordinates. Her customers prefer polygons that can be cut into two halves in a proper way, that is the cut should be straight with starting and ending points in the polygon vertices and both halves should be non-empty and have integer areas. The more ways to cut the polygon in the proper way are -- the more expensive the polygon is.

For example, there are three ways to cut the left polygon in the proper way, and two ways for the right polygon.

The polygons in the shop are always of excellent quality, so the business is expanding. Now Ingrid needs some automatic tool to determine the number of ways to cut the polygon in the proper way. This is very important for her shop, since otherwise you will spend a lot of time on setting prices -- just imagine how much time would it take to set prices for a medium-sized van with polygons. Could you help Ingrid and write the tool for her?

输入格式

The first line of the input contains an integer $n$ -- the number of polygon vertices $(4 \le n \le 200 000)$ . $Each$ of the following $n$ lines contains vertex coordinates: a pair of integers $x_{i}$ and $y_{i}$ per line $(-10^{9} \le x_{i}, y_{i} \le 10^{9}).  The$ specified polygon is convex and its vertices are specified in the order of traversal.

输出格式

Output a single integer $w$ -- the number of ways to cut the polygon in the proper way.

题目大意

按顺序给定一个凸多边形的 $n$ 个定点 $(x_i,y_i)$ ， $x_i,y_i\in[-10^9,10^9]$ 且为整数。

求满足条件的对角线数量，使得该对角线将多边形分成的两个部分的面积皆为整数。

5
7 3
3 5
1 4
2 1
5 0

3

4
1 1
3 1
5 5
1 3

2

提示

Time limit: 2 s, Memory limit: 256 MB.