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 comma 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
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.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@9d5df31:image1.png
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.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@9d5df31:image2.png
There are 11 boundary trees and 17 interior trees. Hence the output is 28.
Answers
Answered by
1
Explanation:
take help from number 9779 874 104
Similar questions