TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 3775,3 "name": "separate_squares_ii",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/separate-squares-ii/",6 "date": "2025-02-01 00:00:00",7 "task_description": "You are given a 2D integer array `squares`. Each `squares[i] = [xi, yi, li]` represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis. Find the **minimum** y-coordinate value of a horizontal line such that the total area covered by squares above the line _equals_ the total area covered by squares below the line. Answers within `10-5` of the actual answer will be accepted. **Note**: Squares **may** overlap. Overlapping areas should be counted **only once** in this version. **Example 1:** **Input:** squares = [[0,0,1],[2,2,1]] **Output:** 1.00000 **Explanation:** Any horizontal line between `y = 1` and `y = 2` results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1. **Example 2:** **Input:** squares = [[0,0,2],[1,1,1]] **Output:** 1.00000 **Explanation:** Since the blue square overlaps with the red square, it will not be counted again. Thus, the line `y = 1` splits the squares into two equal parts. **Constraints:** `1 <= squares.length <= 5 * 104` `squares[i] = [xi, yi, li]` `squares[i].length == 3` `0 <= xi, yi <= 109` `1 <= li <= 109` The total area of all the squares will not exceed `1015`.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "squares = [[0,0,1],[2,2,1]]",12 "output": "1.00000 "13 },14 {15 "label": "Example 2",16 "input": "squares = [[0,0,2],[1,1,1]]",17 "output": "1.00000 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 [24 774609359,25 790622743,26 71431416927 ],28 [29 716559726,30 3913749,31 1181140232 ],33 [34 70635709,35 333822776,36 43728037537 ],38 [39 695937058,40 930578980,41 90242730242 ],43 [44 124096994,45 981219236,46 83745394847 ],48 [49 215047935,50 456173583,51 17427348352 ],53 [54 900777639,55 522709857,56 98816802257 ],58 [59 748671261,60 40927812,61 58288520862 ],63 [64 707296530,65 289554659,66 38369336867 ],68 [69 832013721,70 218369284,71 94704873072 ],73 [74 824959776,75 969737044,76 26423413177 ],78 [79 148676112,80 582314558,81 25676921082 ],83 [84 603566485,85 826499656,86 26866487887 ],88 [89 898194972,90 284546823,91 59115036792 ],93 [94 937293982,95 523470744,96 33409702897 ],98 [99 925750362,100 458485614,101 472958506102 ],103 [104 441730264,105 161611168,106 332134576107 ],108 [109 198154454,110 729557990,111 91510206112 ],113 [114 619905829,115 650577864,116 821323270117 ],118 [119 715476287,120 991712836,121 367733836122 ],123 [124 495948231,125 740405422,126 632133372127 ],128 [129 946906783,130 713812665,131 949318399132 ],133 [134 300571709,135 77162684,136 244791266137 ],138 [139 185122067,140 129809675,141 189506987142 ],143 [144 697484237,145 355684710,146 317577471147 ],148 [149 137482189,150 756979981,151 364276864152 ],153 [154 12359300,155 931122193,156 356944946157 ],158 [159 817393790,160 666159830,161 790413275162 ],163 [164 942567514,165 105521256,166 77915129167 ],168 [169 241334902,170 905877430,171 888814874172 ],173 [174 307703844,175 4306265,176 548187252177 ],178 [179 675336619,180 568111838,181 647130821182 ],183 [184 364287132,185 449328325,186 603949216187 ],188 [189 234350067,190 678772182,191 141294303192 ],193 [194 29392543,195 298334188,196 436386973197 ],198 [199 617025992,200 592618152,201 473299201202 ],203 [204 606196448,205 250127229,206 667898078207 ],208 [209 719495945,210 177627485,211 804759678212 ],213 [214 837312350,215 902416680,216 231452925217 ],218 [219 211662321,220 348876646,221 720609874222 ],223 [224 534654543,225 546041804,226 294840724227 ],228 [229 10602106,230 558884629,231 748556448232 ],233 [234 502954032,235 240729568,236 848481924237 ],238 [239 506328345,240 356405805,241 459008821242 ],243 [244 116431481,245 145256353,246 461404878247 ],248 [249 564626230,250 847454560,251 489299053252 ],253 [254 568270472,255 725978130,256 492015085257 ],258 [259 725494228,260 218674726,261 668196828262 ],263 [264 267167672,265 712312379,266 149011542267 ],268 [269 839534031,270 147012515,271 42571895272 ],273 [274 635842164,275 468874097,276 112973443277 ],278 [279 491964794,280 70480777,281 22005739282 ],283 [284 969059247,285 485481343,286 319484965287 ],288 [289 675875292,290 206203531,291 691704389292 ],293 [294 519365658,295 573049616,296 656504703297 ],298 [299 799023348,300 142623396,301 210057372302 ],303 [304 637218673,305 370379044,306 88831997307 ],308 [309 120585954,310 14723554,311 796198522312 ],313 [314 959503995,315 359265424,316 22265924317 ],318 [319 102176870,320 446871643,321 68052175322 ],323 [324 822888862,325 57979258,326 514164440327 ],328 [329 721108654,330 848514864,331 2078080332 ],333 [334 1156801,335 675952869,336 754921240337 ],338 [339 797481417,340 441205511,341 66575887342 ],343 [344 123188710,345 375169461,346 455117628347 ],348 [349 30074138,350 859905087,351 992575629352 ],353 [354 869558307,355 404128925,356 345126984357 ],358 [359 361758022,360 80337925,361 49338737362 ],363 [364 931005366,365 819614625,366 562285372367 ],368 [369 519101549,370 808685867,371 680251060372 ],373 [374 408501267,375 983346127,376 592862147377 ],378 [379 626540322,380 371993866,381 757992291382 ],383 [384 477871015,385 839614967,386 317565486387 ],388 [389 68148164,390 74202873,391 98881619392 ],393 [394 966555981,395 434532864,396 151862485397 ],398 [399 449912889,400 118307462,401 331999113402 ],403 [404 163474541,405 709835638,406 491639291407 ],408 [409 856405771,410 865696098,411 707122661412 ],413 [414 711756913,415 614559766,416 648484124417 ],418 [419 174503129,420 43306643,421 741374150422 ],423 [424 650480941,425 623239715,426 506853019427 ],428 [429 962220908,430 126199257,431 516054503432 ],433 [434 401593816,435 734055851,436 357125724437 ],438 [439 748453882,440 746681568,441 387437526442 ],443 [444 652458232,445 447353806,446 624967473447 ],448 [449 847809023,450 423631402,451 573613826452 ],453 [454 993872424,455 18203495,456 224847070457 ],458 [459 975693903,460 16172782,461 413581857462 ],463 [464 234319485,465 277833947,466 164852689467 ],468 [469 825636175,470 438958561,471 447829883472 ],473 [474 878195468,475 752189684,476 276961470477 ],478 [479 503575168,480 908238165,481 928701292482 ],483 [484 534845609,485 170357517,486 201514428487 ],488 [489 964158061,490 912625837,491 848201170492 ],493 [494 910055143,495 744896377,496 693178120497 ],498 [499 567111991,500 814960443,501 862406954502 ],503 [504 802675139,505 3845951,506 666183437507 ],508 [509 139310533,510 74304835,511 203955241512 ],513 [514 846959801,515 672532082,516 451468784517 ],518 [519 244202457,520 306296438,521 863592225522 ],523 [524 453903980,525 65873961,526 266521614527 ],528 [529 255535304,530 181799922,531 686779809532 ],533 [534 590829385,535 154523092,536 611821473537 ],538 [539 87594217,540 681407184,541 349421922542 ],543 [544 266777383,545 349641724,546 835301689547 ],548 [549 371653178,550 741267967,551 630365307552 ],553 [554 271109092,555 736697137,556 540326150557 ],558 [559 681400589,560 190994319,561 453396002562 ],563 [564 291879539,565 870272843,566 70489326567 ],568 [569 942454359,570 959522562,571 453897335572 ],573 [574 431353136,575 949448729,576 224341217577 ],578 [579 811723735,580 35842719,581 975360137582 ],583 [584 966839304,585 736545444,586 706630725587 ],588 [589 566003573,590 634319292,591 11777852592 ],593 [594 10508361,595 175759024,596 772193198597 ],598 [599 958303765,600 155173264,601 21186884602 ],603 [604 645371042,605 942559355,606 871221251607 ],608 [609 608406563,610 924706242,611 58284098612 ],613 [614 715167394,615 788840142,616 9327545617 ],618 [619 252307437,620 224552659,621 787470008622 ],623 [624 874474580,625 312862399,626 131392831627 ],628 [629 405362444,630 857196251,631 428847398632 ],633 [634 531627656,635 975771081,636 639414244637 ],638 [639 154081274,640 149314156,641 368543646642 ],643 [644 950732811,645 898339278,646 790587919647 ],648 [649 371139596,650 427150625,651 81904484652 ],653 [654 299700701,655 790916308,656 575073612657 ],658 [659 23944602,660 910912003,661 214492789662 ],663 [664 432019370,665 436022741,666 327604895667 ],668 [669 456597773,670 320107900,671 718810555672 ],673 [674 813699361,675 571516467,676 390220358677 ],678 [679 879838714,680 835564068,681 193107775682 ],683 [684 996589313,685 874153283,686 253536598687 ],688 [689 904892059,690 897609952,691 986716667692 ],693 [694 354885970,695 692856295,696 558688253697 ],698 [699 774136118,700 546337709,701 265100101702 ],703 [704 976142312,705 557117914,706 271620977707 ],708 [709 687501756,710 610879953,711 821927451712 ],713 [714 376910778,715 992593147,716 900181535717 ],718 [719 7291319,720 476609438,721 417011217722 ],723 [724 163648054,725 752945382,726 122571051727 ],728 [729 422324368,730 824603231,731 756162425732 ],733 [734 4776431,735 599951065,736 976906268737 ],738 [739 775079813,740 955256853,741 598673419742 ],743 [744 590702343,745 603747745,746 240513626747 ],748 [749 890200395,750 524525010,751 921749615752 ],753 [754 838833780,755 140730291,756 732632928757 ],758 [759 829828621,760 502882075,761 140255467762 ],763 [764 401339483,765 560860413,766 365502674767 ],768 [769 864483954,770 433390288,771 734712866772 ],773 [774 267181896,775 674150894,776 318467427777 ],778 [779 800809695,780 749190678,781 598039355782 ],783 [784 529718890,785 72354696,786 360866328787 ],788 [789 888371123,790 654171402,791 618715576792 ],793 [794 876727272,795 735468443,796 307052535797 ],798 [799 878544332,800 983533661,801 569244276802 ],803 [804 534803534,805 741734894,806 96664457807 ],808 [809 111532794,810 133279663,811 623108737812 ],813 [814 906939594,815 309599684,816 647249173817 ],818 [819 699276042,820 237886573,821 204823533822 ],823 [824 257894715,825 71855357,826 760164199827 ],828 [829 64242255,830 762171247,831 780418596832 ],833 [834 9820440,835 496662169,836 545364150837 ],838 [839 399530544,840 426870804,841 153078134842 ],843 [844 768874702,845 335953038,846 122639301847 ],848 [849 458171930,850 633525425,851 246761723852 ],853 [854 729051260,855 454862260,856 308951461857 ],858 [859 418567258,860 816594813,861 959674390862 ],863 [864 509545678,865 590234073,866 574697114867 ],868 [869 330220796,870 415171786,871 596360898872 ],873 [874 287493615,875 378446700,876 71316844877 ],878 [879 926138529,880 852448200,881 875588111882 ],883 [884 364931212,885 252081836,886 616613471887 ],888 [889 907401838,890 494413089,891 545662674892 ],893 [894 991353022,895 575325306,896 873163043897 ],898 [899 461324148,900 950878741,901 305284327902 ],903 [904 433175446,905 764289945,906 441551409907 ],908 [909 435037195,910 564390956,911 449525124912 ],913 [914 637249067,915 78958168,916 645950396917 ],918 [919 292953596,920 94750885,921 367726830922 ],923 [924 358291954,925 578685230,926 981007803927 ],928 [929 996010323,930 129918629,931 455437391932 ],933 [934 96789660,935 53184773,936 407848547937 ],938 [939 519684232,940 580001732,941 660976520942 ],943 [944 328938202,945 570664859,946 359335076947 ],948 [949 173389266,950 496615083,951 730860657952 ],953 [954 590044713,955 912008138,956 128171305957 ],958 [959 539625545,960 576539424,961 279993008962 ],963 [964 850691601,965 782311397,966 287628050967 ],968 [969 783911607,970 472546644,971 172387269972 ],973 [974 642087679,975 562036754,976 775752303977 ],978 [979 56842617,980 26774565,981 594802513982 ],983 [984 589997743,985 959880616,986 478388770987 ],988 [989 922891908,990 182394636,991 744691660992 ],993 [994 928947146,995 100864575,996 341094831997 ],998 [999 768300619,1000 968328705,1001 3149802591002 ],1003 [1004 383280671,1005 728096711,1006 4575259011007 ],1008 [1009 87745081,1010 79815855,1011 3475801631012 ],1013 [1014 227741477,1015 613737977,1016 7084856121017 ],1018 [1019 181138284,1020 839925422,1021 1060079711022 ],1023 [1024 352478836,1025 824635497,1026 5736127481027 ],1028 [1029 699141751,1030 508474480,1031 6272968591032 ],1033 [1034 303985075,1035 120492161,1036 3457080251037 ],1038 [1039 966237384,1040 47659302,1041 3394636611042 ],1043 [1044 763050299,1045 353565971,1046 6608798151047 ],1048 [1049 703264444,1050 726477570,1051 7331679951052 ],1053 [1054 843736510,1055 941708992,1056 7886449201057 ],1058 [1059 876983216,1060 510842045,1061 939524721062 ],1063 [1064 23006118,1065 852697882,1066 455649491067 ],1068 [1069 306509366,1070 24010060,1071 3857105771072 ],1073 [1074 144338301,1075 758157107,1076 2192475311077 ],1078 [1079 285269183,1080 233722453,1081 6892189321082 ],1083 [1084 204490649,1085 204648174,1086 2440534741087 ],1088 [1089 473209410,1090 97754673,1091 1749567471092 ],1093 [1094 715781672,1095 549442752,1096 7650715371097 ],1098 [1099 685931724,1100 684943981,1101 1984106381102 ],1103 [1104 374130707,1105 414243188,1106 964157931107 ],1108 [1109 960506640,1110 868190959,1111 5077910081112 ],1113 [1114 685085253,1115 517575430,1116 2001109931117 ],1118 [1119 183607566,1120 586580898,1121 6583650151122 ],1123 [1124 339587530,1125 609949902,1126 5282209221127 ],1128 [1129 386915279,1130 874097647,1131 6071998551132 ],1133 [1134 635614701,1135 779189054,1136 6860683591137 ],1138 [1139 800582357,1140 174510790,1141 6936250091142 ],1143 [1144 372241861,1145 965232840,1146 2398398871147 ],1148 [1149 793937241,1150 571782769,1151 7882688271152 ],1153 [1154 220132458,1155 410144225,1156 55280241157 ],1158 [1159 831030208,1160 235365944,1161 3396030271162 ],1163 [1164 800855012,1165 479039807,1166 3279301831167 ],1168 [1169 590083319,1170 286823801,1171 3894924821172 ],1173 [1174 18303930,1175 140469347,1176 9477201831177 ],1178 [1179 281538642,1180 376475586,1181 764541141182 ],1183 [1184 255948082,1185 519375724,1186 5477563901187 ],1188 [1189 17349334,1190 550450864,1191 123140491192 ],1193 [1194 840280963,1195 976609569,1196 2280780981197 ],1198 [1199 443548440,1200 729278403,