MinimumSquare
SRM 614 · 2013-12-22 · by EmK
SRM 614 · 2013-12-22 · by EmK · Search
Problem Statement
Problem Statement
There are N points in the plane. You are given their description as two
You want to draw a single square onto the plane. The vertices of the square must have integer coordinates, and the sides of the square must be parallel to the coordinate axes. There is one additional constraint: at least K of the N given points must lie strictly inside the square (i.e., not on its boundary).
You are given x, y, and the
Constraints
- x will contain between 2 and 100 elements, inclusive.
- y will contain the same number of elements as x.
- K will be between 1 and the number of elements in x, inclusive.
- All points will be pairwise distinct.
- Each element of x will be between -1,000,000,000 and 1,000,000,000, inclusive.
- Each element of y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
{0, 3}
{0, 7}
2
Returns: 81
The square we seek must contain both given points. One optimal solution is the square with opposite corners at (-1,-1) and (8,8).
1)
{-4, 3, 1}
{3 , -1, -2}
2
Returns: 16
2)
{0, 0, 1, 1, 2, 2}
{0, 1, 0, 1, 0, 1}
4
Returns: 9
3)
{1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000}
{1000000000, 0, -1000000000, 1000000000, 0, -1000000000}
3
Returns: 4000000008000000004
In this case one of the optimal solutions is a square that contains all six points.
4)
{-47881, 28623, 1769, -38328, -16737, 16653, -23181, 37360, 41429, 26282, 254, 728, 8299, -41080, -29498, 17488, -23937, -11, 33319, 25232}
{-46462, 48985, -43820, -19587, -33593, -28337, 13667, -48131, -5568, -2332, -41918, -31370, -3695, 42599, -37788, -40096, 39049, 25045, -2122, 3874}
8
Returns: 1695545329
18)
{933869957, 589685683, -871651175, -219457706, -785131278, -44529216, 487969772, 785653023, 290802873, 216512516, 656216605, 65620486, -510608867, 858243716, 334479094, 992672103, 908247398, -666370921, 352370309, -14752815, -625178726, -117025015, 733665971, 461699408, -14717949, -164824186, -913555856, 968059097, -456079791, 759960609, -50027154, 308804057, -104436231, 375051768, -159754808, 242457215, -381520638, 179226997, -499008948, -436391285, -698949390, 887505349, -295083919, 406374698, -440179031, -200495290, -155028358, -883606409, 81070881, -342763584, -403527501, -511009529, -279730385, 545017295, 710427196, -513525403, -205379064, 449659047, -49009025, -529308812, 284324461, -927076833, -273001060, -211790075, -688850236, 585573349, -136524441, 167708884, 858549449, 306384774, -545628434, 422773043, 274831910, 515642621, -687479160, 580604122, 170423254, -524842350, 783628973, -840151485, 788994062, 705898132, 790784455, -941604648, -203196293, 727664051, 659360528, -104065997, -596610281, 379409516, -383438931, 621701520, 450043787, 881182171, -707360186, 960198038, -261674072, -99118688, 459672184, 556804458}
{494567605, 312158801, -990987051, 422585194, -731596488, -966040034, 548533716, -115539533, -891893836, 441993641, -463564675, -109069983, -241162603, -893477500, -961351953, 812378251, -750722326, -656457315, 666099089, -193038837, -563785195, 53675471, 702007411, 761665130, 294558505, -667182516, -167859288, -509158539, -367787902, -523156775, -580346842, 209697190, 810984407, 995607325, 701334770, -387088760, -13478749, -619122712, 597494532, -622390072, 356036819, 168877486, -394544054, 490612599, 301329945, -225504578, -135503343, -91459735, -640408154, -730984725, 554341523, -253433173, 879818299, -652296083, -772046962, -178501984, 754056826, 133418484, -361917317, -750338848, -455831348, -948800659, 932749289, -743724111, -286727534, 637845935, 172207416, -800058461, 170161517, -983314967, -474463575, -411690942, 183419752, 792565277, 309778838, 885378868, -61472293, 475121499, -440878100, 305056029, -587035965, -419141395, 46884642, -728807369, 215075384, 858541372, 292842841, -918760410, -640286403, 776411598, 53464910, -288440739, 610632567, -868235778, -556940091, -309874090, 592800951, -283479140, -900210452, -823359162}
50
Returns: 1668453577692241561
N=100
19)
{-760157635, 362330270, 605533774, 725707251, -984587764, -950680690, 928463124, -249993920, 256527763, -131152836, 147195411, -548230730, -994166217, -134582935, -856050487, -229855370, 73208258, 916408151, -195373306, 722665650, -264624283, 368806726, 541121723, -998036657, -29157472, -959584712, -960355184, -246898724, 241549684, 563261023, -974756066, -308799705, 719255538, -568963775, -46791076, 96857036, 147972809, -220945420, 599580461, 928304925, -364811427, 841442650, 117055619, 850338050, -506688075, -181681653, -549891822, 185703564, -355953753, -50630807, -366771845, 558090434, 574585847, 31944024, 965154808, -970669791, -243747177, 746373155, -576784543, 662171061, -374270656, -889593266, -850692447, 491321742, -574869298, -193523852, 388229028, -367153147, 426618115, 429079684, 202511397, -141077739, 258990545, 325958750, -409841710, 317193713, 13382900, -175976952, 24274050, -818387164, 839759495, 834032593, 470950274, -769028005, -38542558, -807571385, -774758724, -492544148, 328995258, 181318831, -822127786, -530017609, -544179168, -154432508, -82671180, 987878532, -723698479, 510651859, 308370419, -341468391}
{770495811, -835810751, -947388190, -76191353, -946934326, -120551602, -350504366, 368891459, 971543414, 809097941, -418300404, -217581641, -207419640, -630911919, -191590048, 365726162, -624849384, 704260099, 949911794, -976236150, 325367459, 960677464, -498818748, 119730498, -569970347, -28282224, -93408414, 648310909, 542200390, -400319249, 319580017, 429894559, -144667072, -179702800, -194369128, -119324757, 941832294, -739528834, -936921060, -122097300, 975224008, -492485956, -147048661, -150742145, 558513897, -404950267, -388109581, 414085974, -443400987, 412644128, 380064586, 201976640, -692540001, -436009698, 126685346, 951272845, -653977489, -522000207, 286467711, -173975060, 52569469, 884528756, 13607485, -787299094, 443509958, -698777242, 738669748, 140456594, 319190275, -147803731, 329873499, -984627661, 172157984, -468514377, 46366485, -528086850, -855355305, 202406852, -177127634, 805597398, 72847191, -793152498, 331104494, -635622246, -786915220, -416224647, 563276899, -7940745, -263807975, -208404465, 321649801, -384087737, 521981548, -107509496, -717794299, -428450355, -888508510, 381994942, -355259740, -264552636}
100
Returns: 3943859145844566481
N=100
20)
{368714438, -197576606, -898523384, -69706493, -402169218, 945907810, 243209725, -886442543, -537547869, -117123446, 232786410, 655054169, -83206701, -751205548, 820485206, 556432886, -125866747, -913174424, -548483024, -213377954, 721891949, 691434095, 680267318, -522945490, -962651978, 766778832, 32588188, 988232218, -574498131, -895796263, -189615148, -238866983, 616445825, -852557231, -958767546, 401197348, 612858879, -596187286, -606333970, 988105216, -317225512, -19053707, 6242366, 296766358, 519534982, -255983011, -472256901, -298096315, 941816303, -306984387, -112199602, 996955658, 283563000, -249520433, 859003782, -406087418, 529442218, -807741233, -544241611, 431025410, -765329720, 636218545, -195300177, 905630023, -201735389, 738836201, 490918763, -918573589, 644085101, -436823058, 544356731, -843135017, -996170187, 408856250, 582199489, 219788578, -560705796, 170255696, -110736762, 139154459, -888849683, 885215118, 751573640, -581228932, -884562388, -824840745, -413985322, -518976238, 576549924, -879219511, -475862661, 956566947, -831556380, 268976943, 421880380, -16787276, -854773972, -572549298, -918844276, 753496558}
{480905440, -560878648, -802972094, 631536554, 786003546, 822063482, 100795934, -911776180, 703520227, 113894433, -255664045, 722913034, 564683216, 710207941, -350478585, -791893292, 98529189, -31792672, 705686538, 422252131, -71406048, 115349211, -324194828, -272949737, -294680156, -956083144, 826568748, 620605833, 914908483, 231544674, -615431654, -656792603, 331288752, -678715679, 261812419, -562312824, -112046912, 655229365, -25517694, -582174751, 230084445, -705696131, -701121321, -306676662, 882123741, -576009536, -84801627, 660938032, 482712188, -156497787, -806708540, 226165434, -657710160, 823292289, -531776270, 42362949, 367457728, 239826604, 637247207, 983819886, -324919930, -19978604, -403477720, 380874501, 321063386, -935699569, 604100148, 188070316, 115038469, 840971906, 552875542, 482741974, -173859983, 31374767, -806699712, 612693184, -768551053, -985971106, 702478757, 572029891, 161997745, 637738324, 100573528, 366561004, -242804072, 513855670, -827058471, -371551219, 215552831, -444554988, 558659059, -990534317, 678671787, 586948989, -851349289, -86840317, -949604356, 472415597, 492922077, -14798664}
1
Returns: 4
N=100
67)
{-3315579, -9484212, -2891992, -2675917, -9451178, -5573351, -8768304, -2907784, -8090980, -294122, -8180654, -5608739, -9593263, -2618008, -133324, -678406, -1620723, -1387061, -1162251, -3597253, -3750913, -5142333, -9357775, -9516893, -6661922, -8383065, -5790028, -2190548, -8242843, -8391629, -3674291, -33361, -8096642, -5076299, -4075916, -4638356, -1203173, -5472440, -4510879, -9605522, -8826825, -8796111, -97678, -6432561, -3968140, -6901269, -8329391, -1151494, -4872112, -4023324, -8841341, -3338139, -350489, -8990423, -3945995, -1654103, -6912999, -4148270, -4344521, -7278158, -3837318, -9310261, -4875177, -4388801, -8795821, -9962601, -9535269, -214248, -2546504, -6934272}
{-7613979, -4677193, -9226630, -3058389, -7947333, -5821432, -9445152, -74251, -3316276, -4213073, -6019496, -5260417, -2892342, -1853874, -3483729, -4321365, -4524700, -6529936, -2992207, -3905800, -1421364, -4448618, -6505585, -8632008, -6942010, -1012478, -2248643, -1700292, -3414233, -4546270, -1670008, -6126959, -6565101, -9868001, -6122322, -5982042, -4858176, -9506011, -4400531, -8848430, -4481362, -8897509, -1841052, -9491731, -197765, -7689447, -8962633, -1505728, -6122092, -9739215, -5788534, -5108632, -2547283, -7544780, -8796055, -3396273, -1208908, -4083218, -3346459, -4718334, -4309271, -9952501, -1265186, -136391, -3653244, -4056066, -9094610, -253016, -5999180, -8888544}
42
Returns: 44182928056576
all negative
93)
{503128340, -812436513, -245634101, 167327195, 701524476, -491235444, -592707677, 14017029, 176257227, 78000919, 343015083, -66149208, -765993974, 960561903, -298488643, 622190425, -196461657, 91910869, 122524753, 442788250, 437379492, 530261243, 448450476, -377616789, -378956517, 534434116, 764979257, 720079701, -81044312, 219379605, -878541926, 100818399, -512108175, -673172689, 487521062, 701254672, -234869984, -860498609, -483792318, 572658699, 146250855, -632020668, 821731140, -569142427, 868208532, -281359775, 191833166, 948139348, 68377147, 731225904, 171527050, 7924061, 161493219, 789632042, -495838087, -746910876, 741292425, -911509081, 777936603, -930540289, 132104942, -877016973, 63414127, 159798305, 985945793}
{-503128340, -812436513, -245634101, -167327195, 701524476, -491235444, 592707677, -14017029, -176257227, 78000919, -343015083, 66149208, 765993974, 960561903, 298488643, -622190425, -196461657, 91910869, 122524753, -442788250, -437379492, 530261243, 448450476, 377616789, 378956517, 534434116, -764979257, -720079701, -81044312, -219379605, 878541926, 100818399, -512108175, 673172689, -487521062, 701254672, 234869984, -860498609, 483792318, -572658699, -146250855, -632020668, -821731140, 569142427, 868208532, 281359775, 191833166, 948139348, 68377147, -731225904, -171527050, 7924061, -161493219, 789632042, 495838087, -746910876, 741292425, 911509081, 777936603, 930540289, 132104942, 877016973, -63414127, 159798305, -985945793}
4
Returns: 217975991280100
x
Submissions are judged against all 222 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MinimumSquare with a public method long long minArea(vector<int> x, vector<int> y, int K) · 222 test cases · 2 s / 256 MB per case