| Orchard Trees |
An Orchardist has planted an orchard in a rectangle with trees uniformly spaced in both directions. Thus the trees form a rectangular grid and we can consider the trees to have integer coordinates. The origin of the coordinate system is at the bottom left of the following diagram:
Consider that we now overlay a polygon onto this grid. The vertices of the polygon can have any real coordinates in the range 0.0 to 100.0 (exclusive), thus trees can have coordinates in the range 1 to 99. Two possible polygons (triangles, in this case) are shown.
Write a program that will determine how many trees are contained within a given polygon. For the purposes of this problem, you may assume that the trees are of point size, and that any tree (point) lying exactly on the border of a polygon is considered to be in the polygon.
Input will consist of a series of lines. Each line will contain real numbers in the range 0.0 to 100.0 (exclusive) representing the coordinates of consecutive vertices of a polygon. The format is the following:
Pt1_x Pt1_y Pt2_x Pt2_y Pt3_x Pt3_y ...so that each pair of floating point numbers represents the (x,y) coordinates of a polygon vertex. All coordinates will be presented with one digit of accuracy to the right of the decimal point. If there are 2*N floating point numbers in a line of input, the polygon must have N distinct, nonoverlapping sides. The first pair and the last pair of coordinates on a line of input form a side of the polygon.
You can assume that the polygons will not be degenerate. All will have three or more sides and positive area. No polygon will have more than 10 sides.
Output will consist of one line for each polygon, containing the number of trees contained in (or on) that polygon right justified in a field of width 4.
1.5 1.5 1.5 6.8 6.8 1.5 0.9 0.9 1.1 0.9 1.1 1.1 0.9 1.1
15 1