Statistics

Problem Statement for "WifiPlanet"

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 int[]s x and y, and by the common denominator denom. The ith vertex is (x[i]/denom, y[i]/denom).

Calculate and return the number of routers required.

Definition

Class:
WifiPlanet
Method:
routersNeeded
Parameters:
int[], int[], int
Returns:
long
Method signature:
long routersNeeded(int[] x, int[] y, int denom)
(be sure your method is public)

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.

Examples

  1. {1,7,3,3}

    {1,1,3,5}

    2

    Returns: 2

    This is illustrated in the image below:

  2. {20,99,295,1}

    {100,100,301,301}

    100

    Returns: 3

  3. {100,100,301,301}

    {20,99,295,1}

    100

    Returns: 3

  4. {1234,3000,2345}

    {2345,1357,2999}

    10

    Returns: 11262

  5. {1234,3000,2345}

    {7654,8642,6999}

    10

    Returns: 11271

  6. {8765,7000,7654}

    {2345,1357,2999}

    10

    Returns: 11258

  7. {8765,7000,7654}

    {7654,8642,6999}

    10

    Returns: 11267

  8. {3000,2345,999999999,999999999,1,1234}

    {1357,2999,999999999,1,1,2345}

    10

    Returns: 5000003170181208

  9. {3000,2345,999999999,999999999,1,1234}

    {8642,6999,1,999999999,999999999,7654}

    10

    Returns: 9999958724881435

  10. {3000,2345,999999999,999999999,1,1234}

    {1357,2999,999999999,1,1,2345}

    10

    Returns: 5000003170181208

  11. {7000,7654,1,1,999999999,8765}

    {8642,6999,1,999999999,999999999,7654}

    10

    Returns: 5000005455015417

  12. {2345,1357,2999}

    {1234,3000,2345}

    10

    Returns: 11262

  13. {7654,8642,6999}

    {1234,3000,2345}

    10

    Returns: 11271

  14. {2345,1357,2999}

    {8765,7000,7654}

    10

    Returns: 11258

  15. {7654,8642,6999}

    {8765,7000,7654}

    10

    Returns: 11267

  16. {1357,2999,999999999,1,1,2345}

    {3000,2345,999999999,999999999,1,1234}

    10

    Returns: 5000003170181208

  17. {8642,6999,1,999999999,999999999,7654}

    {3000,2345,999999999,999999999,1,1234}

    10

    Returns: 9999958724881435

  18. {1357,2999,999999999,1,1,2345}

    {3000,2345,999999999,999999999,1,1234}

    10

    Returns: 5000003170181208

  19. {8642,6999,1,999999999,999999999,7654}

    {7000,7654,1,1,999999999,8765}

    10

    Returns: 5000005455015417

  20. {1,999999999,1000000000,2}

    {2,1000000000,999999999,1}

    2

    Returns: 499999999

  21. {1,1,5000,5000}

    {999999999,1,1,999999999}

    512

    Returns: 17578116

  22. {999999999,1,1,999999999}

    {1,1,5000,5000}

    512

    Returns: 17578116

  23. {1,1,1000000000,1000000000,1000}

    {1000000000,1,1,1000,1000}

    255

    Returns: 17535177

  24. {1,1,999999999,999999999}

    {999999999,1,1,999999999}

    2

    Returns: 249999999000000001

  25. {1,1,999999999,999999999}

    {999999999,1,1,999999999}

    1000000000

    Returns: 0

  26. {999,999999999,999999999}

    {999,999999998,1}

    1000

    Returns: 499998500001

  27. {999,999999998,999999999}

    {999,999999999,1}

    1000

    Returns: 499999500000

  28. {900000000,896845881,887433264,871910594,850522672,823606798,791587451,754969596,714330718,670311717,623606798,574952526,525116208,474883792,425047474,376393202,329688283,285669282,245030404,208412549,176393202,149477328,128089406,112566736,103154119,100000000,103154119,112566736,128089406,149477328,176393202,208412549,245030404,285669282,329688283,376393202,425047474,474883792,525116208,574952526,623606798,670311717,714330718,754969596,791587451,823606798,850522672,871910594,887433264,896845881}

    {500000000,550133293,599475955,647249821,692701470,735114101,773818842,808205297,837731170,861930821,880422607,892914900,899210691,899210691,892914900,880422607,861930821,837731170,808205297,773818842,735114101,692701470,647249821,599475955,550133293,500000000,449866707,400524045,352750179,307298530,264885899,226181158,191794703,162268830,138069179,119577393,107085100,100789309,100789309,107085100,119577393,138069179,162268830,191794703,226181158,264885899,307298530,352750179,400524045,449866707}

    13

    Returns: 2966467068680335

  29. {732202482,622733067,789723655,793170685,588191629,513998953,571873430,629996787,589621139,518727741,600324770,573606293,506858504,483508432,433926346,396623706,480201263,466131523,477812997,462460898,380649517,334367195,344311832,463559284,105221348,315798819,496747479,199924434,489822280,347374131,222992714,384403697,497425432,330726890,469218883,441799129,477467359,484547334,516037894,517211724,556230500,601060415,578558862,709329197,651089627,574136886,519246812,565710748,850484541,505763787}

    {500000000,515504792,574388391,616074485,548483758,510170835,567493644,657139121,641220319,539798476,808767892,885857699,609012800,762125975,846370225,818159517,542074458,553368180,526819479,535251564,586713202,591057405,561641306,509356386,549872142,500000000,499589111,422953690,495970355,416093218,298742426,391447846,496887882,233268260,434586797,320876137,381879760,254386910,245084971,409772981,326940316,285235687,376211042,246964468,358117396,446136399,489418975,473983274,410010865,499271864}

    19

    Returns: 247411114006889

  30. {43200,735134405,735134417,11}

    {2,7,735134432,735134413}

    735134400

    Returns: 1

  31. {499760000,500260000,500260000,499800000,499800000,500220000,500220000,499840000,499840000,500180000,500180000,499880000,499880000,500140000,500140000,499920000,499920000,500100000,500100000,499960000,499960000,500060000,500060000,500000000,500000000,500010000,500010000,500050000,500050000,499970000,499970000,500090000,500090000,499930000,499930000,500130000,500130000,499890000,499890000,500170000,500170000,499850000,499850000,500210000,500210000,499810000,499810000,500250000,500250000,499770000}

    {399760000,399760000,400240000,400240000,399800000,399800000,400200000,400200000,399840000,399840000,400160000,400160000,399880000,399880000,400120000,400120000,399920000,399920000,400080000,400080000,399960000,399960000,400040000,400040000,400000000,400010000,400030000,400030000,399970000,399970000,400070000,400070000,399930000,399930000,400110000,400110000,399890000,399890000,400150000,400150000,399850000,399850000,400190000,400190000,399810000,399810000,400230000,400230000,399770000,399770000}

    9973

    Returns: 624

  32. {1,2,5,4}

    {2,3,4,1}

    2

    Returns: 2

  33. {100,100,100,200,200,200,400,400,400,300,300,300,600,600,600,500,500,500,700,700,700,800,800,800}

    {101,102,103,204,205,206,307,308,309,410,411,412,412,411,410,309,308,307,206,205,204,103,102,101}

    100

    Returns: 10

  34. {101,102,103,204,205,206,307,308,309,410,411,412,412,411,410,309,308,307,206,205,204,103,102,101}

    {100,100,100,200,200,200,400,400,400,300,300,300,600,600,600,500,500,500,700,700,700,800,800,800}

    100

    Returns: 10

  35. {4, 14, 14, 17, 9}

    {12, 12, 10, 12, 1}

    7

    Returns: 1

  36. {8, 5, 5, 2, 4, 5}

    {6, 9, 8, 8, 3, 4}

    5

    Returns: 1

  37. {4, 8, 2, 1}

    {3, 6, 5, 4}

    6

    Returns: 0

  38. {626697385, 622403690, 279123985, 196373983, 553461901}

    {226250944, 632825811, 472988849, 11188374, 440030411}

    2

    Returns: 26679724499612340

  39. {66777070, 763404629, 774114879, 765344971}

    {277247043, 684238998, 18911729, 751927098}

    2

    Returns: 6047451401151291

  40. {36878623, 394753729, 97973930, 863680251, 849588982, 866156290, 285249525, 803237699}

    {385631658, 937706800, 974841639, 933982796, 225042793, 135832833, 267242847, 606244971}

    2

    Returns: 101925374388750436

  41. {707823720, 706322567, 578232988}

    {507747727, 758433721, 970521424}

    3

    Returns: 1766215963390818

  42. {748782659, 105524716, 27988209, 451065538, 751368015}

    {777280461, 768667707, 857995743, 290044760, 99383476}

    4

    Returns: 16255611106305534

  43. {496432586, 475260099, 993670127, 991402919}

    {318728045, 217076897, 184099468, 949476180}

    6

    Returns: 6023110998534030

  44. {176821896, 151468589, 151408889}

    {100063703, 194376101, 98315604}

    2

    Returns: 305135215146781

  45. {100063703, 194376101, 98315604}

    {176821896, 151468589, 151408889}

    2

    Returns: 305135215146781

  46. {500000000, 500000001, 499999999}

    {999999999, 1, 2}

    3

    Returns: 0

  47. {50000001, 50000078, 50000059, 50000034}

    {15131302, 81258973, 65276759, 47613063}

    2

    Returns: 31899682

  48. {15131302, 81258973, 65276759, 47613063}

    {50000001, 50000078, 50000059, 50000034}

    2

    Returns: 31899682

  49. {1,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,1}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    2

    Returns: 11999999976

  50. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {1,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,3,999999999,1}

    2

    Returns: 11999999976

  51. {3,3,4,4,5,6,10,10,11,11,10,10,9,9}

    {1,2,2,6,3,8,8,9,9,3,3,2,2,1}

    3

    Returns: 4

  52. {50,1000050,1000049}

    {2,1000002,1000003}

    100

    Returns: 0

  53. {32,32,64,8,15,1000,999}

    {1,10,10,48,48,47,1}

    16

    Returns: 120

  54. {1,1000000000,1000000000,1}

    {1,1,1000000000,1000000000}

    3

    Returns: 111111110888888889

  55. {32, 32, 64, 8, 15, 1000, 999 }

    {1, 10, 10, 48, 48, 47, 1 }

    16

    Returns: 120

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: