Statistics

Problem Statement for "Intersect"

Problem Statement

You are searching for a new house. Location, location, location. You have identified a number of desirable attributes, and for each have sketched a rectangular area that contains all the locations that have that attribute.

You want it all. You need to find the area that is contained in every one of your rectangles. Create a class Intersection that contains a method area that takes as input the collection of rectangles and returns the area of their common intersection.

The collection of rectangles is given by a int[] x and a int[] y. The first two values of x and y specify opposing corners of one rectangle, the next two specify opposing corners of the next rectangle, etc. Thus, each rectangle is the region between its two x values and between its two y values.

Definition

Class:
Intersect
Method:
area
Parameters:
int[], int[]
Returns:
int
Method signature:
int area(int[] x, int[] y)
(be sure your method is public)

Notes

  • the 2 values of x (and of y) for a given rectangle are not necessarily given in ascending order

Constraints

  • x contains an even number of elements between 2 and 50 inclusive
  • y contains the same number of elements as x
  • each element of x and y is between -10,000 and 10,000 inclusive

Examples

  1. {0,2,3,-4}

    {17,1000,18,6}

    Returns: 2

    There are 2 rectangles, one having diagonally opposed corners (0,17) and (2,1000) and the other having diagonally opposed corners (3,18) and (-4,6). The common intersection is the region bounded by x=0, x=2, y=17, y=18 which is a rectangle 2 units wide and 1 unit tall.

  2. {10000,-10000}

    {-10000,10000}

    Returns: 400000000

    There is just one rectangle, so the answer is the area of that rectangle.

  3. {3,8,6,12,10,15}

    {7,17,7,17,7,17}

    Returns: 0

    The first two rectangles intersect each other, and the second and third rectangles intersect each other, but no area is contained in all three rectangles.

  4. {0,0,0,0,0,0,0,0}

    {5,5,5,5,5,5,5,5}

    Returns: 0

    Here we have 4 empty rectangles.

  5. {2,100,5,32,1000,-20,47,12}

    {29,-1000,-800,-200,-900,300,-600,-650}

    Returns: 1000

  6. {1,7,12,3,16,8,3,12}

    {-90,-60,-70,3,-60,-90,-80,-100}

    Returns: 0

  7. {2,3,1,4}

    {6,3,-10,10}

    Returns: 3

  8. {20,30,10,40,25,50}

    {3,6,-10,10,5,-8}

    Returns: 10

  9. {20,30,10,40,30,50}

    {3,6,-10,10,5,-8}

    Returns: 0

  10. {20,30,10,40,20,50}

    {3,6,-10,10,5,-8}

    Returns: 20

  11. {20,30,10,40,29,50}

    {3,6,-10,10,5,-8}

    Returns: 2

  12. {29,-177,-120,31,3,100,50,7}

    {-466,16,-566,-266,-366,26,-666,-16}

    Returns: 2200

  13. {-50,27,0,300,-20,5,-50,300}

    {7500,100,1000,7501,7000,10,10,7501}

    Returns: 30000

  14. {-6520,-1976,7940,9494,-2322,-9034,2229,6002,6945,5815,8862,8994,-5804,8978,-1440,9747,-7138,-1009,-4474,-3180,-5143,3731,6897,-360,8171,2042}

    {9205,7572,-1866,-7270,5762,-7963,8039,5933,-9800,4763,8462,6271,-9388,-4565,6381,-7696,-4681,-6766,-8259,-2789,859,677,1443,8242,-4379,8907}

    Returns: 0

  15. {-3653,-4300,4346,-6884,3961,9904,-1824,5221,-3512,-7656,9944,-9575}

    {441,1735,-9002,6132,-549,6507,-5967,-5115,5784,-8219,566,-6581}

    Returns: 0

  16. {9046,-994,-4914,7176,8519,9710,-6436,3383,-3113,-6927,2010,9793,-7504,3364,4799,4985,-8235,7327,6712,-1955,5632,6480,-2620,2912,9756,6847,-9991,-2871,-7847,5226,4770,5522,7665,-9336,2408,1810,-335,9925}

    {-1061,506,6677,-8290,77,-7952,4759,-8405,-6200,-3800,5200,-1576,-2428,-8171,6883,-2918,-2452,-6956,8505,-7766,-8268,3482,7440,-9213,-2714,-2541,-8617,7626,-4260,9913,-4495,6681,490,-5736,-3446,5157,-8424,-9202}

    Returns: 0

  17. {3349,1499,5001,456,2271,6450,6762,-2117}

    {-2870,-810,2349,2340,-7178,-7720,1160,4740}

    Returns: 0

  18. {3925,9922,7959,887,-4728,-9208}

    {-6713,3516,-2399,-9003,-102,2373}

    Returns: 0

  19. {-3956,2664,-9532,2856,-9424,-630,5540,6490,-6860,-4298,-9026,-8385,-3408,7714,-8448,-1721,1585,-5480,3388,8342,7326,-1130,-3851,3606,7907,7239,9862,7343}

    {6991,-5260,-5826,3161,-8836,6506,-6717,-4097,-1928,7161,-1155,2831,-1886,-9432,-7319,-7066,429,-9820,-8080,-3886,-1704,-3252,-2069,-2364,-3591,-5878,6663,5609}

    Returns: 0

  20. {-3653,4664,-3998,-244,4280,6252,-5792,-3800,8863,-1280,5335,-8159,3445,-4422,-4638,-7080,-2051,3965,-3673,-1087,-4521,3656,-5187,8932,4509,5911}

    {-5409,3397,8084,3713,-7175,-3060,-9234,-2538,-3754,-7001,-2008,7116,3824,-9895,7094,-9319,8087,-1134,-1098,-4310,3650,-5317,-5328,3567,1220,-7003}

    Returns: 0

  21. {-8924,6326,6278,4734,7885,8603,487,-3734,1937,3726,5134,-1836,8061,-8932,2851,-7608,-8846,-1270,-2124,-3348,7199,9724,-3280,-9366,7537,-151,5254,-9762,-7591,-1388,-1062,-5324,6950,-9894,8174,-5271,-1542,2990}

    {-1151,-6466,-9782,1780,-4665,4204,7518,3411,-2586,-5128,-2324,9406,2511,99,-4084,-5776,2731,-3714,-8555,5509,-2992,6352,-2594,5550,6623,-2372,2697,-212,-2563,-2840,3772,-4557,6212,-9351,4216,-5710,-6417,-9539}

    Returns: 0

  22. {780,6954,8340,-3255,1540,8515,-4309,9663,741,4493,5767,-1058,1465,7112,-214,8008,-8841,1597,31,5917,6363,6455,-9850,-6941,-5859,7644,-2148,-8249}

    {-3069,8837,1661,-454,-4986,278,-6142,-717,-4475,-9886,-5055,-2878,4061,-1840,6866,-8207,-8451,3056,7584,6687,-8597,763,-9695,-8143,8725,3177,3318,6243}

    Returns: 0

  23. {2742,-9961,-8537,-2482,6787,2782,-3330,7754,7948,7416}

    {5939,-3787,8203,-8391,-4112,-101,-5443,9485,-9262,7070}

    Returns: 0

  24. {1471,-6907,5726,-3516,6284,-1001,-8324,-3979,-3050,-4207,9222,-3315,6845,6713}

    {-3214,2612,-4501,-7360,-8966,-7171,3214,-1932,-7532,-562,-9974,1115,-4096,2874}

    Returns: 0

  25. {-1803,-6684,-476,7746,-9276,7386,9262,-2193,-7518,-7866,8345,6310,3992,-6436}

    {1350,9529,-8882,2023,4277,-6751,1931,-5190,-9164,-6158,-267,-5030,5368,5476}

    Returns: 0

  26. {9663,-3809,-4898,-7409,8614,-6722,6457,-4193,-6588,-9730,-6239,6011,4009,-2502,6187,-6603,1735,-9738,6222,-6053,-4103,-9893,-5851,-1563,4131,-464,-6777,-6501,8989,6370,3522,2571,-5740,-8429,5353,9001,-152,2838,-1448,-4694,-1155,5803,-1178,9182}

    {7753,-2557,2085,-3513,-1187,4563,6487,5824,-642,-3681,9964,1560,-1019,-2352,3397,-4368,6163,76,6505,6397,-9920,-351,-1321,5609,-9590,5858,6280,-6835,-9883,9422,-6141,5511,5244,-9597,2631,8027,6483,8875,428,-4518,-6006,1346,-6820,-751}

    Returns: 0

  27. {3234,-3748,726,-8168,-9360,373,-9138,-9358,-8015,-6531,1789,-4349,4427,-2747,8346,6006,2378,9199,5768,-7094}

    {7493,6702,-6731,-1152,4870,-840,2942,-39,-3249,-3302,-254,3382,2438,-4788,-7492,-7296,9145,-497,-978,-87}

    Returns: 0

  28. {1313,-6853,-8539,-5963,-5833,9046}

    {1466,-5713,7596,6127,8630,7412}

    Returns: 0

  29. {7611,6862,-21,-6307,-3791,2931,2982,-2205}

    {529,-9231,1016,-4514,-9252,-2510,-977,-3968}

    Returns: 0

  30. {-7760,8159}

    {7710,7228}

    Returns: 7672958

  31. {8745,-3918,170,-297,5483,301,-3157,7691,3294,-5696,7455,5270,8502,-7930,-5017,8042,172,-8776,-889,-122}

    {1457,8637,795,-8090,8800,1550,2800,7862,9927,5936,4181,-2804,-1748,-4074,3729,-5985,3145,-5015,-1070,2184}

    Returns: 0

  32. {-3312,-9695,3949,-6711,-5638,-5141,-4911,7496,-4465,-3158,1603,8527,4974,-2454,-2518,-6357,6808,8133,-9050,6342,-5205,2711}

    {-9947,-9681,4163,333,4302,3580,4103,-7831,8299,-8628,5359,-2604,-5762,7003,7268,-9826,8984,1561,5909,-4096,3501,-6546}

    Returns: 0

  33. {4817,-2154,-2604,7211,-4136,4776,-9278,5600,9539,6549,4852,-1017}

    {5910,-6285,273,-9702,3327,3647,-7297,-3710,7877,4606,-2639,-8825}

    Returns: 0

  34. {-421,1393,-167,-1988,9661,-5944,-8520,-4335,3475,-4440,-824,3543,-8325,6474,6990,-8006,4944,-9821,-4992,-4664,6010,8569,7114,3903,-1409,8467}

    {-8287,-5874,-2210,-3730,-1128,4716,-9688,8587,8874,4426,-3703,4224,8295,8894,-6467,-5422,-3743,3362,-3875,-3190,-5122,-9309,-3408,8206,-8493,2545}

    Returns: 0

  35. {-4597,-3195,4675,6750,-7122,-5820,4441,8731,4467,8138,6485,8813,-7114,5275,-9683,-8622,-2178,4246,-7542,-4018,-683,-7774,903,-3012,9154,3800,-9156,5869,131,-5034}

    {40,-3045,-9057,8161,-992,-5352,-3054,6645,6894,-2121,-2040,-4129,4948,703,-5450,3754,-4818,-9604,-629,632,8036,-2450,8729,8372,-9224,8391,2199,4893,8582,-9049}

    Returns: 0

  36. {7449,2017,-1380,-432,-4369,-7231,7366,5196,-5070,-9789,5395,8276,-248,1915,8820,9798,-8149,1399,-7526,-9834,-6564,3697,-9951,2185,-3977,-8638,6651,2199,-9402,-9401,-9213,-8092,7281,-5408,-9618,-9100}

    {5833,5220,-7420,7842,-9601,6995,-3765,-4377,5582,4154,-2794,-8726,3787,-3821,2718,852,4638,-2493,5064,-1140,8638,5626,146,4155,4119,7362,8931,4020,2815,-3352,-7634,8185,1740,-6102,-5857,-7055}

    Returns: 0

  37. {3051,-207,-3369,-8221,-9025,1257,-2751,-6012,2563,6575,5832,-3723,2004,-8745,-4372,-144,3088,-4307,-1489,8328,-1725,6537,3315,1565,-7224,-2469,-4478,-5638,7056,4100,-8677,-6522,5018,-2593}

    {365,2498,-8676,731,-6327,8573,6786,1877,-8614,-9008,-7548,-5794,3695,6882,-742,7082,7935,-4317,3108,-611,-698,4869,-4992,-4088,-5395,-5041,-8446,3189,-2584,6641,-9732,-2771,-1187,-9685}

    Returns: 0

  38. {-6538,2067,215,-7470,9957,867,1417,4559,-8429,6357,-2299,-7607,-364,-3776,7546,-9331,-7662,-9454,-8131,85,2167,66,-2976,4079}

    {6927,-3807,-7356,5622,4447,1028,4398,8286,-7286,-9458,-4150,-9861,2946,-9899,-540,-4623,847,-8307,-8948,-4857,3120,-1021,149,-5356}

    Returns: 0

  39. {95,-4374,584,-3253,4964,9108,-3661,-3804,-9208,-2272}

    {744,-4003,-3540,-8742,259,-6793,-2493,-6870,-2612,-7301}

    Returns: 0

  40. {691,-9706,5327,7996,-1682,4452,9,-5730}

    {-4890,6474,1381,-7379,3058,-4292,-7869,-9102}

    Returns: 0

  41. {-372,330,3653,6910,2096,-3656,-9157,-8395,3797,3369}

    {523,-8573,4862,4530,1295,2565,8709,9406,9064,9902}

    Returns: 0

  42. {-8152,-5458,-8364,-4308,7765,5296,-3602,2115,-2698,7885,8009,-5132,8986,8100,-835,-8062,-9246,-1212,-5089,-1982,-8409,8014,10000,5621,9870,1521}

    {8133,876,-3184,-6400,-3709,-9610,3291,-9375,-7925,-9856,160,5295,296,5658,-527,1880,9646,-9458,-2862,3771,207,9004,-3973,9479,-9884,1623}

    Returns: 0

  43. {-3206,9502,-6474,-572,-8789,-1425,-7065,-7977,2320,-9608,-4955,-4830,7128,-1340,6207,-218,-1064,5083,-5957,-4488}

    {-3073,7717,3374,3504,-6177,2612,6260,-9035,-8656,3927,6527,-4558,2534,-7249,-3238,-2881,8949,-4266,5610,-9958}

    Returns: 0

  44. {-7017,895,951,-9118,-8512,-8348,60,5543,-4334,-4567,3088,6779,-9046,7397,-5019,6112,191,7225,541,5683,2822,-878,5901,6783,-5303,-7598,-9675,-8526,-8814,-682,3480,-6729,-4624,8988,4451,-2757,946,-9477}

    {6003,6149,8404,-1498,6155,8385,9340,786,-4629,4722,8348,-4299,5892,-3385,8001,-6978,1770,-6588,22,-649,-6773,5776,-5250,-720,279,-9378,-4829,3688,-367,419,-6345,8484,-3386,-6551,-7056,8523,-2766,7553}

    Returns: 0

  45. {6779,2689,3227,122,4542,3582,-9588,-7473,-2385,-1428,4484,-5645,9924,-1742,6239,8245}

    {3534,4260,4950,-7938,8544,-9318,5844,9022,-9153,2107,1772,5783,5978,-1130,1422,7261}

    Returns: 0

  46. {-9613,-1988,-4888,8143,-1437,58,321,-950,5132,-8799,-2682,-9850,-3562,-3551}

    {-7877,-2375,-4675,8136,5801,8056,3663,-2305,143,-4408,1047,6865,-9145,8930}

    Returns: 0

  47. {-227,-4483,-3754,-2760,9082,4608,-2029,-3036,1574,6573,-6182,1529,263,2940,7440,9444,-875,3652,3620,7696,6820,-758,5157,-5944,7823,4660,-824,3806,4291,-2396,994,3718,3057,-2829,8588,377,946,-5449,762,7655,-351,-9606}

    {4341,5379,7314,6875,-9302,-2610,-6136,81,1572,7266,2548,-2785,-226,7138,1682,-2432,-9756,3398,9847,-2812,3237,-6308,9709,-7415,-6866,1899,6284,950,-4363,5721,6907,2222,7109,-2057,-4840,-2036,453,-8740,-1566,-777,-6237,1737}

    Returns: 0

  48. {3578,6211,-3927,7434}

    {497,-4034,-3866,-8416}

    Returns: 442344

  49. {-6591,7270,-1532,4374,-4985,-9430,-8829,-9806,5453,-1033,-9477,3665,3770,-9934,-1638,-5323,6922,533,-9257,-5634,-9294,-605,-3076,-8764,-4016,-3338,-9411,3822,-1704,-299,8485,2812,-9906,-4633,-8921,6903}

    {2270,-3288,-7635,-9833,-944,7622,-5985,-6983,-5306,5829,-621,-4851,-9474,7357,2195,4612,-1141,2963,-6136,-767,-1509,8157,-9778,1087,8233,3119,-2391,-7826,-6936,5621,-3411,-6568,5537,-6215,-5334,-6020}

    Returns: 0

  50. {-6316,9348,2659,2206,5525,7562,5339,-8785,1479,5656,3081,-9867,1235,763,-1273,6533,-3808,-9781,-5737,6442,6900,4074,-8923,1299,8696,-8740,-3311,2955,-117,2373,2600,2706,-3724,-6381,4846,39,-778,3972,5782,3853,4970,-8902}

    {3579,112,4850,-2221,-2483,5420,9101,-4799,8872,4343,372,5397,9953,-3594,-142,9731,-2248,-1561,7820,-5425,-7007,-2748,8589,8289,-5801,1270,1936,-4340,5673,3516,838,-6149,8702,-4126,9311,-9215,-3963,2700,8207,-1631,-3911,-5526}

    Returns: 0

  51. {-7895,-5998,-6916,8487,-8878,6862,2076,5378,-1906,4173,9787,-6592,-8450,-143,1852,-279,6584,2001,-1354,4804,-7344,2727,486,6546,9977,3899,-4018,8333,1343,-2204,-350,911,8688,-8734,-8965,3678,9959,3330,3457,-6699,3573,-8166,8433,5759,-4777,1115}

    {1271,-1278,-5250,6025,-1835,-8056,-5620,4696,-9960,-4774,-9759,-1901,-1248,-8948,8647,7627,9492,-7920,4636,2711,9878,-8013,2866,-3558,-259,-3670,207,-3314,431,-5931,-2346,-4174,-6470,1536,-5950,2247,6828,4411,-4232,6377,-9470,9385,282,5836,5217,9613}

    Returns: 0

  52. {-5977,3589,-7374,-3821}

    {5263,8037,-6257,8219}

    Returns: 5980744

  53. {-3210,-5862,-3968,2509,1626,8365,-7975,-6366,3220,-6702,4907,-9167}

    {1973,659,7719,7394,-5738,-6830,-7043,6506,-187,-2433,-2272,8546}

    Returns: 0

  54. {9112,-2784,8345,5084,-4907,-229,3858,-4360,9808,-2912,-8489,-6575,-3453,-1304,5101,-3007,5254,8910}

    {-202,8881,-1934,-5286,-2347,-2641,5524,-5689,9017,635,-2163,-6560,-9739,2898,-2554,6702,-5064,-1849}

    Returns: 0

  55. {5772,-2001,-9761,-3478,1352,-2624,-806,1711,8707,-8106,9048,2428,2395,1111,9633,-8221,-8909,-7231,7910,3657,-7682,950,-6978,3434,-1681,-1931,7893,5894}

    {-4409,2702,8002,-9702,1034,-2126,6318,5159,-3318,-6254,1546,2536,-3822,-3636,6045,-9478,-3349,-9578,705,4937,4174,97,9738,8700,3476,2058,-3024,2126}

    Returns: 0

  56. {2483,-5354,184,698,8826,-8242,9147,6413,7384,-4514,-9497,-6316,6962,-2158,-1134,-53,2413,-891,-6457,-9775,9089,7211,4613,-3912,-3813,8599,2353,-235,8527,4630,-6080,-2956,-1834,-2204,6897,-8564,8242,1273,9914,1486,-132,-988}

    {-5904,7100,-7411,8666,5033,-4315,694,4639,-4459,-8837,-1201,2141,-7019,-7357,-9940,7512,8309,-6550,8340,1876,3226,1062,3005,227,-2115,360,721,-651,-3074,2475,3928,-8592,-524,2245,6292,4917,4574,-6688,-8892,-1966,-3165,-3108}

    Returns: 0

  57. {179,-3427,-3968,5984,2133,-8837,-2658,-1801,6038,717,-5182,1423,-7781,5153,7897,8148,-4922,421,-6306,1839,-4483,-3959,2578,6790,1073,-4091,-9636,196,242,7697,4083,-9329}

    {5340,2606,-1154,-5428,-8937,-9649,1423,-5083,-5824,-3675,311,-8477,4180,-3040,4892,-8878,6096,-387,-1831,4961,9895,6886,7740,-4277,-5636,5102,-7961,-6931,2634,-5278,-8426,-7852}

    Returns: 0

  58. {8195,4888,-9571,-6271,-5442,-3529,6140,-973,-115,-536,5884,-6813,8332,-1356,-3435,-5476,-2273,-2832,-1364,367,5516,-6616,-8407,9867,-7846,-1523,2376,7037,1965,5713,-4164,5017,9928,-8097,9340,-942,-9239,-5730,3953,-6716,3616,-4420,4846,-1294}

    {2267,7565,-7867,-7420,-460,-7081,-1635,948,-3224,3545,-6412,-4167,2589,-2253,-1117,-7946,-3068,-5332,3098,-4699,6683,-5415,9318,3566,-554,-9214,5291,-209,5419,2450,1435,-8588,-1718,4880,2227,4455,8405,-1273,2409,-5896,-4975,2500,-7420,-925}

    Returns: 0

  59. {-794,-245,-1523,-4679,4074,-4927,3693,-7674,6515,-6603,8351,-805,-9634,4224,-18,3822,6667,4675,-1355,-2043,5150,5121,1810,-4396,4359,-4572,-6031,9135,-4125,-3745,-1478,7698,1071,3477,8593,-5712,8532,8528,-8616,7303,4334,-5883,-2319,-3734,8018,-581,7584,9938,8969,-3348}

    {-9497,-3224,-7745,-7673,2705,8276,-1126,-7769,2542,9135,-7747,-7679,-4146,-6386,4719,-3495,2462,-1522,-1004,-2555,-8642,-9487,6591,-2280,-340,2878,8882,-3855,4554,9005,1907,954,2070,9846,5907,-1753,1082,-5838,5376,3661,5410,-8261,7696,-9864,-5441,584,1750,5692,2149,-7289}

    Returns: 0

  60. {-2667,5698,5800,9979,9128,-4017,1351,7822,-3847,2585,-6540,-8748,-1166,1941,6646,450,6028,-3467,-1069,-3144}

    {-9585,-9544,3510,7284,-8799,-7495,8769,4111,7922,-1132,-7208,-6479,-7187,4533,-8538,-9512,1364,2838,8949,-7724}

    Returns: 0

  61. {6466,8671}

    {1824,-3258}

    Returns: 11205810

  62. {-5779,3065,-3468,-6708,1526,7182,4551,4808,8577,-6192,6835,7035,-3061,28,249,5548,3293,8180,-9994,2693}

    {2285,6685,-9876,378,-6808,-8041,4141,4756,3645,6802,-1498,-9453,-1014,-9873,-5304,-8011,4385,8941,4396,8336}

    Returns: 0

  63. {8212,-9975,8858,7921,-1013,-9979,-3630,-4408,1506,1853,-8911,-5003,6668,3306,3287,3708,2722,-8436,1100,-6721,1051,-2831,2624,-3011,-5385,-3201,9052,5801,5827,-5219,421,3714,727,-6200,-4740,2611,-4146,3927,4366,3100}

    {-1858,-1241,3752,-3810,4668,-7886,7622,-592,6452,-6862,-1987,505,-81,5428,2626,1830,1032,-6952,2940,-2920,1259,5756,3449,8539,7133,-277,8436,4837,-9671,2843,-8944,1792,-4430,-3530,-1785,-6238,-5702,7677,986,-5611}

    Returns: 0

  64. { 2, 100, 5, 32, 1000, -20, 47, 12 }

    { 29, -1000, -800, -200, -900, 300, -600, -650 }

    Returns: 1000

  65. { 1, 7, 12, 3, 16, 8, 3, 12 }

    { -90, -60, -70, 3, -60, -90, -80, -100 }

    Returns: 0

  66. { 0, 4, 6, -8 }

    { 4, 8, -6, 9 }

    Returns: 16

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: