MockVita 2018 Problem: Lattice Disks

Lattice Disks

Problem Description

Consider the lattice of circular disks each of which has center at a point (i, j), 0 <= i, j<=N, and radius 1/2. A convex polygonal line is drawn through the centers of these circles. Consider all the disks that are either completely inside the polygonal area or whose centers are on the boundary of the polygon. Find the total number of these disks that lie within the polygon.

In the figure above, the polygon is ABCDEFGA, and the points H, I and J are centers of disks that lie on the boundary. In the figure above, the portion of the areas of the disks marked y that lie inside the polygon should not be counted whereas those disks marked x must be included.

Constraints

N<=30

k<=12

Input Format

The first line of the input is a positive integer N, the size of the grid (number of disks on each row and column of the grid)

The next line has a single positive integer k, the number of vertices of the polygon.

The next k lines contain a set of four non-negative integers, giving the x and y coordinates of the starting and ending vertices in one segment of the polygon. Note that the segments may not be given in any order

Output

One line giving the number of disks in the polygon, using the counting method described above (if the polygon goes exactly through the center, or the disk is entirely within the polygon, count the disk)

Test Case

TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

  Explanation

Example 1

Input

8

4

2,1,1,7

1,7,6,8

6,2,2,1

6,2,6,8

Output

26

Explanation

The polygon and related disks are shown below.

There are 17 disks wholly within the polygon ABCD, 4 at the corners (A,B,C,D) and 5 through whose centers the line CD goes exactly through, giving a total of 26. Hence the output is 26

Example 2

Input

8

5

6,1,2,1

3,6,1,4

5,5,6,1

5,5,3,6

2,1,1,4

Output

19

Explanation

The polygon ABCDE is shown below

There are 10 internal disks in the polygon ABCDE. The disks on the side between B and C, those between D and E, and those between E and A are all partially cut, and not counted. Apart from the 5 vertices (A, B, C, D and E), the line AB goes through the centres centers of 3 disks (F, G, H) and the side CD goes through the center of 1 disk (I), which all need to be counted. The total number of disks to be counted is 10 + 5 + 3 + 1=19. Hence the output is 19.