MockVita 2018 Problem: Orchard

Orchard

Problem Description

There is a large orchard containing apple trees that is coming up for sale. You want to bid for the same but you need to count the number of trees in the orchard so that you can arrive at a reasonable bid. The orchard is quite huge. While the boundaries are straight lines, the area covered by the orchard is a polygon. The polygon is simple (the sides will not intersect) but may not be convex (the interior angles may be more than 180 degrees) However, if you introduce a coordinate system inside the orchard, with the origin at a tree, all the trees are uniformly located at all points whose both coordinates are even integers. (Note that an integer is said to be even if the absolute value is even; hence -6 and 0 are even, -3 is not). The corner points of the boundaries are also at points whose coordinates are even integers. Given the coordinates of the corner points of the boundary, write a program to count the number of trees in the orchard.

Constraints

4<=N<=50

Input Format

The first line contains an integer N which gives the number of boundary corners.

The next N lines each contain two commas separated integers giving the coordinates of the boundary corners in clockwise order (so that the interior of the orchard is always on the right when going from one point to the next).

Output

One integer giving the number of trees in the orchard (including the trees on the boundary).

Test Case

TestCase 1
8
5
6,1,2,1
3,6,1,4
5,5,6,1
5,5,3,6
2,1,1,4

19

TestCase 2
8
4
2,1,1,7
1,7,6,8
6,2,2,1
6,2,6,8

26

  Explanation

Example 1

Input

7

-4,-2

-4,2

-6,6

2,2

8,4

6,-4

6,2

Output

17

Explanation

The polygon AGFEDCB is shown below. Trees are planted at points where the x and y coordinates are even, and the corner points are also even.

As can be seen, the number of trees on the boundary are 11, and the number of trees in the interior is 6, giving a total of 17 trees.

Example 2

Input

7

-2,-4

-4,-6

-6,4

0,0

6,6

8,-6

4,-4

Output

28

Explanation

The polygon ABCDEFG is shown below. The trees are on the corner points and the boundary and interior points which have both x and y coordinates even.

There are 11 boundary trees and 17 interior trees. Hence the output is 28.