WifiPlanet
SRM 410 · 2008-07-19 · by bmerry
Problem Statement
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 boundary.
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
Calculate and return the number of routers required.
Constraints
- 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.
{1,7,3,3}
{1,1,3,5}
2
Returns: 2
This is illustrated in the image below:
{20,99,295,1}
{100,100,301,301}
100
Returns: 3
{100,100,301,301}
{20,99,295,1}
100
Returns: 3
{1234,3000,2345}
{2345,1357,2999}
10
Returns: 11262
{1234,3000,2345}
{7654,8642,6999}
10
Returns: 11271
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WifiPlanet with a public method long long routersNeeded(vector<int> x, vector<int> y, int denom) · 55 test cases · 2 s / 256 MB per case