Dissatisfied with the inconvenient spherical shape of the Earth, a group of
map-makers have gone to Magrathea to obtain a custom-built planet. They
decided to design their new planet to be flat and in the shape of a polygon.
All coordinates will be in the Cartesian (x, y) plane.
In order to provide everyone on the planet with internet access, a wireless
router will be placed at every lattice point that is inside the polygon (a
lattice point is a point with integer coordinates). The map-makers decided to
keep their job simple by choosing a polygon with no lattice points on its
Because the map-makers are highly rational people, they decided that the coordinates of all the
vertices of the polygon would be fractions with a common denominator. The vertices of the
polygon (in order), are given by the ints x and y, and by the
common denominator denom. The ith vertex is
Calculate and return the number of routers required.
|Parameters:||int, int, int|
|Method signature:||long routersNeeded(int x, int y, int denom)|
|(be sure your method is public)|
|-||x and y will contain the same number of elements.|
|-||x and y will each contain between 3 and 50 elements, inclusive.|
|-||Each element of x and y will be between 1 and 10^9, inclusive.|
|-||No two vertices of the polygon will be the same.|
|-||No two edges of the polygon (including their end-points) will intersect, with the exception that adjacent edges will intersect at their common end-point.|
|-||No lattice point will lie on the boundary of the polygon.|
|-||denom will be between 2 and 10^9, inclusive.|
This is illustrated in the image below: