Integral Polygons#9441
Ingrid runs a polygon shop in a faraway country. She sells only convex polygons with integer coordinates. Her customers prefer polygons that can be cut into two halves in a proper way: the cut must be straight, must start and end at vertices of the polygon, and both halves must be non-empty and have integer areas. The more ways there are to cut a polygon properly, the more expensive the polygon is.
For example, there are three ways to cut the left polygon properly, and two ways to cut the right one.
The polygons in the shop are always of excellent quality, so the business is expanding. Now Ingrid needs an automatic tool to determine the number of ways to cut a polygon properly. This is very important for her shop, since otherwise she would spend a lot of time setting prices — just imagine how long it would take to price a medium-sized van full of polygons. Could you help Ingrid by writing this tool for her?
The first line contains an integer n~(4 \le n \le 200000), the number of vertices of the polygon. Each of the next lines contains the coordinates of a vertex: two integers x_i and y_i~(-10^9 \le x_i, y_i \le 10^9).
The given polygon is convex, and its vertices are listed in traversal order.
Print one integer : the number of ways to cut the polygon properly.
Example 1
Example 2