Statistics

Problem Statement for "CheckerPolygon"

Problem Statement

A convex polygon is placed on a large checkerboard with the polygon vertices lying on the grid intersections. Calculate the number of light and dark squares lying entirely inside the polygon. Assume that the polygon edges are infinitely thin. In the picture below, 28 light squares and 26 dark squares are enclosed by the polygon. The upper left corner (coordinates 0,0) will always be a dark square.


Create a class CheckerPolygon containing the method countSquares which takes two int[], X and Y, describing the convex polygon. Element i in X and Y is the coordinate for the ith vertex in the polygon. The method should return a int[] containing exactly two elements: the first element is the number of light squares entirely enclosed by the polygon, and the second element the number of dark squares entirely enclosed by the polygon.

Definition

Class:
CheckerPolygon
Method:
countSquares
Parameters:
int[], int[]
Returns:
int[]
Method signature:
int[] countSquares(int[] X, int[] Y)
(be sure your method is public)

Notes

  • The vertices in the polygon may be ordered clockwise or counter-clockwise.

Constraints

  • X and Y will contain between 3 and 50 elements, inclusive.
  • X will contain the same number of elements as Y.
  • Each element in X and Y will be between 0 and 10000, inclusive.
  • The polygon described by X and Y will be convex.
  • There will not be three points lying on the same line.

Examples

  1. {1,2,5,8,11,10,6,4,2}

    {7,5,2,1,2,8,11,11,9}

    Returns: {26, 28 }

    This is the example in the problem statement.

  2. {1,5000,5001,10000,10000,5001,5000,1}

    {4999,0,0,4999,5000,9999,9999,5000}

    Returns: {25000000, 24990001 }

  3. {1,3,6}

    {3,6,1}

    Returns: {1, 1 }

  4. {537,127,987,2390}

    {173,98,12,107}

    Returns: {90908, 90911 }

  5. {10000,10000,0,0}

    {0,10000,10000,0}

    Returns: {50000000, 50000000 }

  6. {0,1,9999,10000,10000,9999,1,0}

    {1,0,0,1,9997,10000,10000,9998}

    Returns: {49999996, 49999997 }

  7. {537,537,538}

    {537,538,538}

    Returns: {0, 0 }

  8. {0,10000,10000,0}

    {5000,5001,5002,5001}

    Returns: {0, 0 }

  9. {3000,3001,3002,3001}

    {0,10000,10000,0}

    Returns: {0, 0 }

  10. {419,390,339,275,237,217,175,108,97,64,36,21,5,5,11,18,30,64,75,128,178,229,293,338,390,508,522,535,536,534,506,497,478,464}

    {51,33,14,5,6,9,23,60,70,103,146,180,253,273,332,352,384,438,450,496,520,534,536,528,508,392,355,286,273,242,148,133,104,89}

    Returns: {108946, 108975 }

  11. {792,478,464,410,248,223,146,88,5,14,32,40,173,278,411,492,545,741,1214,1464,1500,1539,1671,1676,1692,1689,1687,1667,1598,1555,1504,1470,1387,1330,1304,931,802}

    {6,90,97,127,255,282,380,483,802,977,1063,1088,1356,1471,1569,1614,1635,1685,1610,1427,1383,1335,1033,1013,833,777,756,644,460,389,318,278,200,155,138,8,6}

    Returns: {1097729, 1097725 }

  12. {753,797,2173,2218,4321,6324,6626,7495,7704,8162,8379,8364,8316,8043,7773,7603,7557,6302,5433,5210,5160,4984,2613,2286,2195,439,352,312,183,38,29,35,183,223,373,384,738}

    {6584,6646,7863,7887,8380,7799,7603,6770,6477,5531,4039,3808,3451,2542,2017,1759,1697,573,191,129,116,79,312,462,510,2332,2519,2613,2977,3655,3731,4705,5408,5531,5913,5937,6562}

    Returns: {26844460, 26844464 }

  13. {3259,1690,1411,1373,794,665,651,598,572,149,129,13,79,84,426,1878,2530,3384,3789,4070,4171,4934,5084,5883,6113,6158,6225,6400,6528,6815,7834,7939,8068,8173,8304,8333,7771,7408,7099,5976,5502,4273,4146,3763,3384}

    {8238,7518,7293,7259,6613,6422,6401,6313,6269,5258,5184,4427,3384,3359,2344,692,341,80,22,5,4,74,106,372,485,508,546,651,736,951,2185,2390,2696,3011,3636,3968,6269,6795,7136,7928,8120,8338,8339,8319,8263}

    Returns: {26799271, 26799384 }

  14. {6031,6039,6277,5501,4862,4290,4199,4125,3286,3151,2363,1747,1712,1427,932,202,41,42,798,1192,1781,2439,2879,3557,3938,4199,4254,4627,5641}

    {4523,4505,3767,1030,496,209,176,152,6,4,109,342,360,527,932,2067,2686,3653,5266,5641,6014,6248,6321,6311,6239,6162,6142,5979,5147}

    Returns: {15186188, 15186154 }

  15. {505,503,472,386,193,14,39,134,149,160,357,504}

    {249,227,130,41,12,322,382,474,482,486,483,279}

    Returns: {82161, 82185 }

  16. {2577,2997,3072,3340,4028,4023,3984,3587,1918,1540,858,848,674,675,1316,1709}

    {84,260,303,502,1955,2164,2433,3273,4026,3972,3661,3655,3516,518,130,28}

    Returns: {5377714, 5377726 }

  17. {2705,2399,2199,2175,1997,1712,790,365,170,160,125,105,16,61,121,222,345,358,393,660,696,1150,1431,1688,1783,2352,2376,2705,3099,3454,3600,3613,3709,3896,3794,3782,3761,3739,3660,3631,3513,3446,3265}

    {156,56,19,16,4,18,386,819,1161,1183,1272,1328,1724,2422,2616,2846,3050,3070,3118,3408,3439,3724,3825,3878,3889,3854,3849,3743,3520,3184,2981,2960,2781,1961,1328,1294,1238,1183,1022,970,790,706,515}

    Returns: {5866752, 5866773 }

  18. {3873,4001,5317,6887,7039,7374,7748,7761,8183,8236,8270,8284,8340,8343,8332,8269,7812,7707,7439,5918,5777,5513,4179,3822,1395,405,266,79,889,1338,2701}

    {8343,8350,8196,7357,7220,6868,6348,6326,5367,5169,5019,4943,4537,4486,3745,3340,2122,1946,1571,384,323,223,5,20,1069,2395,2725,4969,6748,7239,8083}

    Returns: {26656482, 26656507 }

  19. {324,377,1056,2948,3988,4920,5219,5301,5781,5833,6041,6568,6712,7468,7686,8922,8911,8706,8678,7890,6946,6760,5489,5084,4070,2692,533,482,65,4}

    {2819,2692,1599,275,31,26,65,80,197,213,285,520,599,1146,1355,5056,5138,5964,6041,7385,8220,8336,8844,8918,8940,8586,6592,6494,5219,4481}

    Returns: {30287619, 30287554 }

  20. {9,127,209,250,288,254,249,225,84,29,9}

    {157,10,18,46,161,244,251,271,275,228,164}

    Returns: {26938, 26916 }

  21. {532,625,662,824,861,883,913,957,971,982,1014,1026,1027,1019,1013,999,950,904,877,816,703,541,460,318,286,229,199,156,90,60,32,13,5,6,60,77,99,206,248,275,304,408,479}

    {4,16,25,107,137,159,192,256,281,303,395,457,557,610,644,686,787,851,881,931,993,1027,1026,989,974,941,918,881,801,746,683,607,554,473,287,253,219,109,81,65,52,16,5}

    Returns: {407661, 407663 }

  22. {876,614,418,368,303,259,81,61,37,10,6,10,104,153,216,274,450,470,519,573,639,678,943,951,965,1017,1052,1128,1151,1164,1167,1165,1152,1136,1093,1020,996}

    {1091,1165,1144,1125,1095,1064,872,831,775,668,615,523,260,203,140,99,24,18,10,5,8,12,130,136,148,196,237,374,449,512,597,654,717,771,869,975,1001}

    Returns: {520099, 520077 }

  23. {4646,2123,1096,684,441,213,10,518,1713,1932,2175,2769,3244,4044,5328,5386,5438,5924,5955,5918,5900,5098}

    {507,135,682,1097,1440,1898,3171,4661,5686,5779,5859,5965,5962,5778,4838,4766,4691,3516,2660,2425,2335,879}

    Returns: {13380723, 13380789 }

  24. {345,7032,7753,7527,6862,6760,5672,4994,2110}

    {5540,1504,2941,5585,6589,6691,7485,7736,7428}

    Returns: {13351655, 13351722 }

  25. {2611,2865,3255,3659,3859,4382,4667,4808,4834,5181,5168,4608,4526,4493,4287,4177,3616,3438,3302,3006,2817,2358,1347,799,7,52,150,190,234,592,952,1092,1236,1416,1619,1951}

    {5186,5173,5099,4956,4858,4472,4151,3940,3900,2738,2279,965,867,833,634,544,215,147,102,39,15,15,327,731,2517,3085,3453,3557,3659,4239,4598,4703,4802,4903,4996,5105}

    Returns: {10272913, 10273088 }

  26. {7128,8459,8498,8566,8202,7827,7391,7021,6890,6711,5840,5738,3799,3746,2836,2299,1506,1346,934,819,744,349,99,78,27,69,217,414,461,575,672,1233,1385,1691,2275,3455,3746,3906,5941,6890,6956}

    {965,2761,2861,3065,6549,7106,7581,7892,7988,8107,8526,8560,8733,8726,8489,8242,7689,7545,7085,6935,6824,6091,5296,5191,3959,3639,3039,2539,2442,2228,2067,1347,1195,932,547,107,52,33,289,790,837}

    Returns: {29368766, 29368666 }

  27. {7328,6690,6370,6333,1787,1310,1119,218,16,183,312,1329,2625,6589,6841,7243,7769,7816,7743,7483}

    {1993,1155,864,833,640,1005,1187,2648,3635,5082,5444,6856,7620,6793,6535,5997,4663,3491,3065,2292}

    Returns: {21924289, 21924280 }

  28. {4581,5074,6626,6964,7352,7799,7822,8067,7696,7684,7486,7223,5901,5855,5833,5485,5076,4705,3305,2772,1829,1602,1173,1019,505,398,336,80,501,876,2040}

    {33,128,873,1174,1602,2330,2374,3061,6081,6103,6424,6762,7785,7807,7817,7962,8086,8155,8124,7978,7510,7352,6965,6799,6057,5857,5720,3330,2150,1585,563}

    Returns: {25508833, 25508861 }

  29. {2791,2579,362,80,4186,6105,6537,6932,6729,6062,4410,3914}

    {213,286,2395,3296,8117,7567,7274,1193,1009,533,19,8}

    Returns: {19095451, 19095458 }

  30. {851,898,1062,1078,1125,1143,1409,1420,1422,1405,1403,1389,1303,1283,1159,1131,1109,1083,897,701,593,487,442,438,350,245,209,167,136,92,25,14,10,8,88,107,112,224,261,327,485,688,748}

    {20,29,98,105,136,149,589,644,710,859,872,923,1107,1131,1264,1284,1298,1313,1395,1420,1411,1385,1369,1367,1321,1243,1212,1162,1125,1055,886,821,743,666,379,350,343,206,169,120,47,4,6}

    Returns: {770577, 770565 }

  31. {937,672,505,464,194,37,9,5,6,77,134,614,830,1331,1589,2089,2271,2773,2887,3132,3585,3790,4364,4617,4888,4994,5919,5942,6039,6182,6168,6087,5968,5829,5808,5197,5040,4919,4826,4398,4381,4206,3954,3790,3510,2792,1723,1347,1255,1019}

    {883,1180,1410,1474,2037,2641,2924,3094,3189,3752,3973,4934,5198,5631,5791,6017,6071,6167,6178,6185,6144,6105,5912,5783,5609,5528,4346,4294,4027,3038,2792,2326,1966,1655,1623,831,694,602,536,295,286,212,129,83,34,19,327,548,614,805}

    Returns: {14835277, 14835262 }

  32. {23,5,9,10,17,23,31,51,109,120,288,382,515,819,868,904,1060,1094,1108,1242,1263,1270,1309,1340,1373,1374,1373,1354,1351,1328,1149,1130,1110,1055,939,790,752,731,602,447,428,348,275,227,110,59}

    {536,648,769,781,819,848,880,940,1052,1070,1245,1302,1352,1362,1351,1339,1266,1242,1232,1094,1063,1052,982,904,727,689,652,528,511,443,182,166,150,111,52,11,7,6,10,48,57,95,145,185,323,420}

    Returns: {727651, 727641 }

  33. {6,6,12,21,34,82,406,430,567,593,690,1043,1218,1784,2345,2378,2475,2621,2613,2579,2552,2501,2453,2407,2364,2319,2124,2106,2005,1631,1306,897,696,655,489,166,81,61}

    {1306,1361,1457,1521,1584,1745,2255,2276,2388,2407,2463,2593,2616,2535,2118,2073,1916,1313,1154,980,896,761,668,593,535,478,288,272,206,46,6,76,159,183,296,691,881,942}

    Returns: {2634784, 2634860 }

  34. {328,494,539,822,839,972,992,1147,1171,1270,1311,1365,1373,1375,1391,1394,1374,1282,1275,1244,1210,929,913,880,750,729,683,670,237,157,131,97,60,47,9,10,12,54,62,97,131,200}

    {112,35,23,15,20,62,70,167,192,303,368,498,527,539,640,708,859,1078,1089,1130,1168,1355,1361,1369,1391,1392,1393,1392,1216,1134,1100,1045,969,937,776,619,594,446,427,354,299,218}

    Returns: {741808, 741790 }

  35. {367,623,1482,3148,3590,4339,4334,3721,2414,1569,829}

    {1903,3579,4680,4747,4520,3906,1195,847,337,524,788}

    Returns: {7206798, 7206797 }

  36. {1761,4848,5800,5230,2369,1811,130}

    {6163,4779,3352,2335,1209,1109,4021}

    Returns: {8702346, 8702349 }

  37. {600,335,83,358,501,1026,1381,1791,2067,2295,2204,1808,1241}

    {439,647,1004,1992,2053,2241,2346,2226,1921,904,734,350,226}

    Returns: {1726158, 1726160 }

  38. {545,404,250,170,154,167,179,441}

    {405,190,167,255,309,473,572,583}

    Returns: {61203, 61205 }

  39. {445,826,1338,1441,1336,1256,978,566,343,260,115,285}

    {1396,1476,1032,743,512,390,200,98,171,222,450,1264}

    Returns: {647989, 648006 }

  40. {4742,5256,4957,1838,1015,616}

    {1727,4203,4269,4825,4685,1520}

    Returns: {6184705, 6184704 }

  41. {4487,4384,3733,3327,2070,1676,1027,213,279,2031,2656,4026}

    {2462,2155,773,353,344,392,717,1783,2529,4330,4338,3397}

    Returns: {6060198, 6060209 }

  42. {4526,4823,5300,5912,5958,6437,7140,7155,7085,6691,6273,5820,5460,4777,4488,4273,3027,2707,2108,1985,836,640,50,14,54,324,424,1268,1751,1889,2228,2493,3398}

    {151,229,454,876,923,1461,3092,3530,4401,5399,5934,6411,6664,6965,7071,7115,7131,7053,6844,6796,5860,5623,3878,3661,3269,2170,1925,863,518,448,294,186,11}

    Returns: {19743634, 19743625 }

  43. {1415,3914,5032,5627,8906,9219,8306,6451,2973,1612,199}

    {1681,706,473,735,3241,3998,6902,8286,8835,7646,3848}

    Returns: {26570220, 26570199 }

  44. {4494,4739,4622,4488,4187,3560,2594,1364,1341,698,229,301,413,602,1038,2137,3014,3726,4061}

    {1411,3027,3333,3566,3934,4665,4926,4648,4628,3826,3081,1495,1239,1013,610,290,140,577,888}

    Returns: {8252386, 8252359 }

  45. {1068,837,1157,1519,1748,4285,7027,7596,7613,6016,4932,1758}

    {5405,4863,3245,1660,682,157,2506,3668,5022,6946,7558,6084}

    Returns: {17602034, 17602071 }

  46. {5832,5699,5439,4186,3904,780,282,19,241,335,677,979,1632,3280,4438,5819}

    {3501,3930,4503,5568,5679,4932,4185,2676,1864,1652,1107,776,375,82,455,3335}

    Returns: {12035592, 12035593 }

  47. {5038,4976,4797,2578,805,1125,3822,4279,5026}

    {2774,3946,4418,5389,3071,1493,917,1021,2126}

    Returns: {6850558, 6850541 }

  48. {1370,1228,633,366,1143}

    {612,1118,1627,329,97}

    Returns: {476044, 476046 }

  49. {176,144,98,54,35,17,56,100,133,161,200,222,232,227}

    {22,7,13,26,45,166,214,230,237,231,209,183,115,82}

    Returns: {18953, 18941 }

  50. {185,118,143,224,803,942,1566,2159,2772,2913,2852,2366,2286,1649,444}

    {2217,1777,1091,839,250,194,6,198,763,1240,1823,2638,2707,2993,2415}

    Returns: {3087053, 3087060 }

  51. {1472,654,289,884,1163,4253,3809,3345,2745}

    {3533,3213,2419,656,422,1628,2729,3528,3544}

    Returns: {4296216, 4296213 }

  52. {3032,2025,1190,70,151,496,1325,2811,2993,3319}

    {547,144,165,1498,2272,3159,3766,3530,3128,1783}

    Returns: {4518912, 4518910 }

  53. {5356,5545,4812,1166,777,5243}

    {1504,2034,5028,5120,4401,1496}

    Returns: {4629814, 4629820 }

  54. {4340,1342,602,279,413,2427,3386,6248,6251}

    {5908,5413,4263,2442,2293,975,587,3051,3221}

    Returns: {10386077, 10386070 }

  55. {1623,2552,3385,3472,3615,3503,2848,1821,1011,804,379,291,230,594}

    {3692,3576,2824,2638,1931,1379,267,21,317,406,920,1122,2674,3123}

    Returns: {4794376, 4794384 }

  56. {95,92,158,292,553,675,847,726}

    {665,421,307,209,68,247,947,919}

    Returns: {198003, 198004 }

  57. {3124,3159,3060,2545,1685,685,352,368,423,1695,2210}

    {1667,2858,3044,3162,3217,2935,2235,1443,1154,68,111}

    Returns: {3374085, 3374084 }

  58. {4939,4214,3096,2107,1718,496,495,734,3793}

    {3630,1843,185,246,719,2369,3912,4128,4213}

    Returns: {6397782, 6397785 }

  59. {994,1825,3720,5271,6724,6673,6341,5849,5330,4610,3507,2558,2275,867,262,685}

    {1054,439,53,770,2503,3213,5119,5938,6331,6660,6681,6342,6206,5006,3133,1508}

    Returns: {16142100, 16142117 }

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: