Statistics

Problem Statement for "RedAndBluePoints"

Problem Statement

Fox Ciel likes blue points and hates red points.
There are some blue points and some red points in a two-dimensional plane. Ciel wants to draw a convex polygon. The polygon must not contain any red points. On the other hand, it should contain as many blue points as possible. A point on the boundary of a polygon counts as being contained in the polygon. The polygon is allowed to be degenerated: a point and a single line segment do also count as polygons.
You are given four int[]s: blueX, blueY, redX and redY. For each valid i, there is a blue point with coordinates blueX[i] and blueY[i]. The red points are described in the same way by redX and redY.
Return the largest number of blue points a valid polygon may contain.

Definition

Class:
RedAndBluePoints
Method:
find
Parameters:
int[], int[], int[], int[]
Returns:
int
Method signature:
int find(int[] blueX, int[] blueY, int[] redX, int[] redY)
(be sure your method is public)

Constraints

  • Both blueX and blueY will contain B elements.
  • Both redX and redY will contain R elements.
  • Both B and R will be between 1 and 50.
  • Each element of blueX, blueY, redX and redY will be between 0 and 1000.
  • No two points will be in the same exact position.
  • No three points will lie on the same line.

Examples

  1. {0,0,10,10}

    {0,10,0,10}

    {100}

    {120}

    Returns: 4

    There's a square of blue points, and the only red point is outside the square, so the answer is 4.

  2. {0,0,10,10}

    {0,10,0,10}

    {3}

    {4}

    Returns: 3

    In this case, we have one red point inside the square so we can't use the four blue points, we're only allowed to use 3 of them, that may be for example (0,10), (10,0) and (10,10) to form a triangle.

  3. {0,0,10,10}

    {0,10,0,10}

    {3,6}

    {2,7}

    Returns: 2

  4. {0}

    {0}

    {1}

    {1}

    Returns: 1

  5. {5, 6, 6}

    {9, 0, 5}

    {7}

    {6}

    Returns: 3

  6. {10,20,30}

    {1,4,9}

    {40,50,60}

    {16,25,36}

    Returns: 3

  7. {0, 3, 3}

    {9, 0, 7}

    {5}

    {8}

    Returns: 3

  8. {0, 4, 0, 6}

    {1, 6, 6, 8}

    {7}

    {2}

    Returns: 4

  9. {4, 6, 9, 7, 8}

    {0, 5, 4, 8, 8}

    {3}

    {2}

    Returns: 5

  10. {971,966,403,780}

    {557,264,395,385}

    {915,410,993,454,580,515,970}

    {857,415,871,598,228,766,251}

    Returns: 4

  11. {659,606,755,850,56,394,780,822,68,493,603,647,529}

    {223,872,33,545,298,240,785,320,239,15,982,450,174}

    {561,999,770,266,96}

    {60,452,883,83,545}

    Returns: 12

  12. {304,42}

    {889,489}

    {899,393,501,433,781,399,839,786,619,209}

    {246,535,57,73,773,216,4,282,13,216}

    Returns: 2

  13. {962,297,10,529,933,766,480,709,545,124,806,561,478,523}

    {821,205,687,456,612,603,99,696,4,305,385,666,498,398}

    {251,359,831,772,337,979,842,91,986,903,864,747,119,421}

    {298,339,573,232,689,102,551,814,382,212,396,1000,29,819}

    Returns: 10

  14. {604,404,206,291,245,547,935,546,887,987,316}

    {661,904,737,587,324,221,724,814,225,154,42}

    {77,126,670,915,536}

    {623,614,737,222,339}

    Returns: 7

  15. {581,890,230,539,915,962,612,897,27,204,442,566,508,246,509,737,593,996,888}

    {272,592,54,826,55,622,285,620,635,731,349,99,367,880,378,725,54,447,821}

    {86,604,469}

    {932,272,100}

    Returns: 15

  16. {665,216,788,709,269,753,953,578,548,102,256,689,737,350,342}

    {638,51,328,490,262,364,320,709,443,874,613,475,842,903,355}

    {859,674,828,285,645,865,108,184,41,203,511}

    {713,536,293,742,751,276,608,974,165,315,352}

    Returns: 8

  17. {20,271,883,503}

    {165,167,752,678}

    {335,784,461}

    {520,885,109}

    Returns: 4

  18. {749,519,763,52,262,3,990,4,670,248,969}

    {651,754,655,973,16,967,755,813,419,808,551}

    {847,957,730,526,158,15,952,552,737,375,410,797}

    {916,565,972,605,428,184,763,707,32,792,422,151}

    Returns: 6

  19. {696}

    {311}

    {529,926,634,507,184,997,242,519,977,617,448,853,576,168,1,403,809,905}

    {122,542,870,409,360,1000,945,1000,707,661,798,879,897,747,644,286,617,141}

    Returns: 1

  20. {70,981,162,948,271,287,731,567}

    {791,725,129,532,591,9,293,276}

    {69,712,908,353}

    {427,390,451,957}

    Returns: 6

  21. {612,457,123,112}

    {577,175,832,121}

    {388,159}

    {482,545}

    Returns: 3

  22. {815,903,927,148,71,239,738,523,815,257,760,891,237,754,902,582,913,640}

    {392,438,686,669,239,75,337,955,366,884,173,454,438,65,303,573,693,635}

    {570,188,516,467,666,972,687,683,787,10,585,964,889,211,591,786,780,894,855}

    {606,894,107,21,915,388,615,677,376,161,361,326,653,90,285,627,674,382,399}

    Returns: 6

  23. {983,58,739,76,488,106,629,473,111}

    {530,860,15,535,33,790,398,614,237}

    {760,758,959,479,717,599,250,888}

    {182,495,425,754,375,955,989,576}

    Returns: 8

  24. {932,69,231}

    {816,144,609}

    {857,807,211,451,906,996,561,920,94,358,135,727,544,631,434,70,699,974,951}

    {802,720,367,844,381,511,172,713,69,697,444,77,232,53,598,875,624,152,182}

    Returns: 2

  25. {109,317,611,190,455,706,318,913}

    {693,871,809,244,889,444,869,930}

    {35,398,162,776,748,48,86,819,396,375,251,557,863}

    {177,177,146,489,406,214,543,883,376,713,843,201,959}

    Returns: 6

  26. {567,18,462,338,446,898}

    {36,40,255,605,327,782}

    {661,600,277,142,929,487,3,632,694,285,216,450}

    {3,339,0,905,411,230,859,279,520,858,66,884}

    Returns: 5

  27. {799,573,890,340,907,957}

    {727,742,289,51,17,518}

    {754,584,730,484,621,235,790,849,437,442,121,147}

    {683,581,322,322,272,889,448,731,188,100,660,796}

    Returns: 4

  28. {541,970,810,83,396,909,791,874,536,662,431,110,274,901,38,167}

    {350,721,775,498,751,444,718,97,484,962,598,803,620,239,588,312}

    {569,949,167,765,466,281,36,44,653,467,705,466,299,641,208,381,203,616,226}

    {257,479,611,254,530,150,497,501,983,409,456,988,808,780,262,601,260,622,214}

    Returns: 7

  29. {608,758,88}

    {387,691,35}

    {125,369,645,783,224,927,199,134,318,136,381,955,464,680,919,695,927,601,411}

    {884,964,895,807,176,925,402,147,918,989,143,16,532,76,513,229,557,533,674}

    Returns: 2

  30. {658,960,635,870,625,161,780,473,669,938,602,63,454,772,140,150,137,972}

    {336,61,873,610,343,651,84,911,389,157,815,673,820,52,376,927,489,10}

    {858,673,579,364,497,252,958,892,589,558,435,783,834,123,827,379,673,739,130,31,17,806,23,404,395,276,372,983,495,918}

    {514,859,457,17,859,345,850,118,738,828,578,295,180,91,957,695,913,906,666,738,963,563,461,997,38,998,715,227,768,182}

    Returns: 8

  31. {331,735,539,720,258,378,576,318,561}

    {849,426,187,924,451,532,529,746,425}

    {420,325,197,929,557,408,898,464,816,926,251,453,48,232,342,492,804,603,886}

    {427,900,457,930,728,774,974,363,313,271,965,334,466,385,933,207,229,490,367}

    Returns: 6

  32. {472,670,285,233,97,57,790,395,843,552,34,588,339,816,8,409,193,853,338,645,489,323,245,592,805,729,3,111,955,86,940,63,154,366,984,678,897}

    {107,270,611,804,304,525,356,168,948,957,270,165,264,33,389,7,380,824,905,631,986,628,18,655,170,949,851,32,530,455,769,875,147,83,900,724,21}

    {447,62,983,668,317,897,12,551,964,329,393,207,90,822,614}

    {965,910,767,684,990,872,768,307,663,684,61,480,313,605,853}

    Returns: 14

  33. {979,191,226,637,456,792,664,906,866,509,733,135}

    {794,203,249,932,565,234,393,29,464,318,384,971}

    {879,664,974,425,302,191,404,605,947,949,892,574,152,157,445,415,249,796,851,249,134,576,748,862,814}

    {281,649,85,459,960,629,115,980,287,568,287,197,747,884,457,129,936,36,664,851,536,381,174,683,918}

    Returns: 7

  34. {291,469,468,164,96,135,44,505,331,504,745,987,762,413,162,77,551,622,474,867,180,175,566,132,94,328,234,267,246,760,949,512,806,551,919,594,256,1,333}

    {985,807,420,443,482,966,645,981,578,860,589,782,672,58,831,950,938,359,7,633,793,427,231,827,288,618,772,277,559,929,495,720,622,27,924,249,505,879,461}

    {14,81,596,96,816,883,802,874,122,963,52,873,47,694}

    {326,639,102,245,909,127,242,990,617,514,701,385,301,348}

    Returns: 31

  35. {467,873,889,149,725,142,473,326,661,307,391,92,89,30,625,604,671,547,740,875,277,107,336,124,717,521,10,275,396,474,922,48,6,470,97,31,646,209,680,385,185,277,835,395,207,658,774,239,68,439}

    {768,51,641,714,828,852,220,24,451,368,4,384,554,136,339,279,272,516,900,590,701,162,192,792,90,734,51,373,517,331,839,464,52,743,869,19,928,488,514,823,377,115,706,506,565,697,31,918,52,624}

    {702,180,907,836,153,441,223,163,768,108,735,894,462,400,303,710,254,980,818,926,372,289,493,161,132,271,797,486,24,378,59,790,945,904,894,33,989,855,507,614,201,328,35,104,484,727,834,240,311,502}

    {223,290,834,8,233,654,621,173,124,344,840,617,288,869,529,375,949,701,690,698,382,264,502,989,883,111,63,704,751,376,174,359,276,986,87,761,55,337,435,587,323,30,224,163,619,115,980,451,577,996}

    Returns: 11

  36. {476,995,862,817,529,480,976,655,306,877,819,680,573,286,984,637,356,353,696,207,612,776,796,173,658,768,55,886,131,945,556,274,737,596,358,303,262,209,808,243,638,191,13,675,338,69,320,406,988,206}

    {980,741,471,344,400,691,963,17,667,708,886,155,264,850,718,812,339,430,963,484,762,335,305,469,18,192,520,780,20,146,136,68,355,262,211,795,456,342,223,428,366,19,336,474,770,835,40,702,735,289}

    {654,849,54,152,618,175,590,513,851,576,345,633,648,791,341,792,735,836,468,477,417,50,737,841,36,756,957,440,358,260,692,158,333,895,349,76,861,140,10,315,334,613,559,579,761,901,158,976,512,131}

    {621,236,688,751,933,220,84,860,148,343,125,433,693,378,986,535,322,875,985,682,940,754,861,676,66,832,113,799,559,812,294,566,835,375,883,808,188,894,260,238,692,371,12,207,307,510,573,56,105,668}

    Returns: 14

  37. {194,446,210,944,756,141,632,435,82,123,492,16,911,969,334,376,322,232,494,741,491,277,639,452,264,204,202,501,593,340,381,968,397,448,263,154,9,508,393,409,469,890,390,113,691,40,936,434,809,639}

    {317,674,97,532,461,177,538,872,342,421,355,696,72,237,441,659,296,313,746,306,59,650,563,419,509,896,620,425,596,677,526,807,343,438,333,916,930,704,571,981,958,793,538,659,12,632,602,882,177,546}

    {912,947,460,185,547,111,472,86,875,895,652,23,109,114,643,762,381,177,488,102,258,318,208,790,155,737,893,456,543,747,166,502,669,928,4,302,568,384,390,14,790,469,22,245,248,8,671,213,589,612}

    {956,303,135,51,800,664,491,769,892,654,76,387,692,121,15,688,971,676,425,767,729,950,879,52,788,165,417,946,377,198,908,98,915,333,983,88,785,389,40,871,442,416,574,675,674,527,56,881,627,349}

    Returns: 22

  38. {0, 0, 10, 10 }

    {0, 10, 0, 10 }

    {3 }

    {4 }

    Returns: 3

  39. {0 }

    {0 }

    {1 }

    {1 }

    Returns: 1

  40. {6, 0, 5, 10 }

    {0, 10, 5, 10 }

    {5 }

    {6 }

    Returns: 3

  41. {0, 100, 100, 0, 50 }

    {0, 0, 100, 100, 2 }

    {50 }

    {1 }

    Returns: 4

  42. {0, 1 }

    {0, 0 }

    {1 }

    {1 }

    Returns: 2

  43. {42, 170, 963, 282, 996, 392, 293, 719, 772, 668, 704, 674, 254, 663, 724, 317, 289, 265, 891, 7, 630, 757, 932, 627, 119, 834, 705, 674, 925, 778, 987, 356, 32, 942, 108, 458, 946, 222, 507, 901, 411, 549, 603, 375, 349, 282, 419, 128, 311, 310 }

    {468, 725, 465, 828, 943, 605, 383, 896, 539, 300, 812, 665, 869, 758, 742, 36, 107, 649, 730, 102, 624, 841, 309, 324, 83, 116, 931, 387, 73, 574, 291, 768, 53, 725, 192, 288, 910, 589, 31, 592, 360, 484, 351, 21, 200, 735, 939, 468, 618, 617 }

    {335, 479, 706, 962, 828, 903, 422, 448, 870, 36, 323, 142, 548, 38, 530, 191, 41, 447, 371, 394, 85, 967, 945, 538, 930, 640, 978, 22, 271, 98, 162, 656, 351, 967, 8, 754, 210, 423, 414, 763, 625, 596, 292, 597, 669, 54, 901, 729, 814, 936 }

    {501, 359, 146, 492, 437, 154, 717, 727, 913, 895, 334, 712, 645, 860, 779, 843, 943, 806, 351, 549, 955, 377, 440, 539, 542, 659, 307, 746, 830, 513, 637, 575, 151, 431, 338, 384, 759, 947, 169, 656, 538, 42, 837, 22, 485, 1000, 789, 894, 515, 452 }

    Returns: 14

  44. {0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841 }

    {0, 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 }

    {1000 }

    {999 }

    Returns: 30

  45. {383, 886, 777, 915, 793, 335, 386, 492, 649, 421, 362, 27, 690, 59, 763, 926, 540, 426, 172, 736, 211, 368, 567, 429, 782, 530, 862, 123, 67, 135, 929, 802, 22, 58, 69, 167, 393, 456, 11, 42, 229, 373, 421, 919, 784, 537, 198, 324, 315, 370 }

    {413, 526, 91, 980, 956, 873, 862, 170, 996, 281, 305, 925, 84, 327, 336, 505, 846, 729, 313, 857, 124, 895, 582, 545, 814, 367, 434, 364, 43, 750, 87, 808, 276, 178, 788, 584, 403, 651, 754, 399, 932, 60, 676, 368, 739, 12, 226, 586, 94, 539 }

    {795, 570, 434, 378, 467, 601, 97, 902, 317, 492, 652, 756, 301, 280, 286, 441, 865, 689, 444, 619 }

    {440, 729, 31, 117, 97, 771, 481, 675, 709, 927, 567, 856, 497, 353, 586, 965, 306, 683, 219, 624 }

    Returns: 20

  46. {0, 100, 0, 1 }

    {0, 0, 100, 1 }

    {2 }

    {3 }

    Returns: 3

  47. {0, 6, 3, 3 }

    {0, 0, 3, 6 }

    {4 }

    {1 }

    Returns: 3

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: