PolylineCover
SRM 801 · 2021-02-22 · by misof
SRM 801 · 2021-02-22 · by misof · Geometry, Math
Problem Statement
Problem Statement
You are given a collection of polylines. Each polyline has a total length at most 200,000.
Pick a single rectangle that matches the constraints below and can be used to cover each of the given polylines. For each of the given polylines show how your rectangle can be shifted and rotated so that it contains the entire polyline. (Arbitrary rotation is allowed, not just multiples of 90 degrees.)
Constraints on your rectangle:
- The length of each side is a real number that is at least 100.
- Its area is at most 2*10^10.
- For each placement of the rectangle, each coordinate is a real number in [-10^9, 10^9].
The collection of N polylines is described as follows:
- You are given the
int[] L with N elements: the lengths of the polylines. - You are given the
int[] s X and Y with their coordinates: the first L[0] elements of X are the x-coordinates of points on polyline 0, the next L[1] elements of X are the x-coordinates of points on polyline 1, and so on.
Return a
Make sure that you always use the same rectangle and report its same three vertices in the same order. I.e., in each sextuple the distance between (x0,y0) and (x1,y1) must be the same, the distance between (x1,y1) and (x2,y2) must be the same, and at (x1,y1) we must always turn 90 degrees to the right when going from (x0,y0) to (x2,y2) along the rectangle boundary.
Notes
- A valid solution always exists, and you may return any one of them.
- When the grader compares lengths or areas, it accepts if a relative error at most 1e-9 can make the comparison correct.
- When the grader checks a right angle, it uses atan2 to compute it and then accepts if it's within 1e-9 relative error of pi/2.
- When the grader checks whether a point lies inside your rectangle, it accepts if a point shifted by 1e-3 towards the center of your rectangle lies inside.
- The points described by X and Y are not necessarily distinct. In particular, consecutive points on the same polyline may also be identical.
Constraints
- L will contain between 1 and 50 elements, inclusive.
- Each element of L will be between 2 and 50, inclusive.
- sum(L) will be at most 250.
- X and Y will have sum(L) elements each.
- Each element of X and Y will be between 0 and 10^6, inclusive.
- The total length of each polyline will be at most 200,000.
Examples
0)
{2}
{10, 200010}
{10, 10}
Returns: {0.0, 0.0, 0.0, 100.0, 1.23456789E8, 100.0 }
A single polyline that consists of a single line segment: from (10,10) to (200010,10). We cover it using a rectangle that is long and narrow.
1)
{2, 2}
{10, 200010, 10, 10}
{10, 10, 200010, 10}
Returns: {0.0, 0.0, 0.0, 100.0, 1.23456789E8, 100.0, 90.0, 10.0, -10.0, 10.0, -10.0, 1.23456799E8 }
Two polylines: one is a horizontal line segment, the other is a vertical line segment. We used the same rectangle as before but now we rotated it differently for each of the polylines.
2)
{2, 2, 4}
{10, 200010, 10, 10, 0, 30000, 60000, 90000}
{10, 10, 200010, 10, 0, 30000, 0, 30000}
Returns: {0.0, 0.0, 0.0, 30000.0, 300000.0, 30000.0, 30000.0, 0.0, 0.0, 0.0, 0.0, 300000.0, 0.0, 0.0, 0.0, 30000.0, 300000.0, 30000.0 }
We now added a third polyline that is a zigzag of length approximately 169705.63. We need a shorter fatter rectangle if we want to cover all three.
3)
{2, 2, 3}
{1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1}
Returns: {0.0, -85.0, -85.0, 0.0, 0.0, 85.0, 0.0, -85.0, -85.0, 0.0, 0.0, 85.0, 0.0, -80.0, -85.0, 5.0, 0.0, 90.0 }
Each of these polylines has length 0 = it's just a single point. Covering single points is rather easy, but it may be a special case for some types of solutions. We used a square rotated by 45 degrees (and shifted one of its copies a bit just because we can).
4)
{4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}
{517672, 519106, 598018, 603632, 401946, 448906, 369926, 389483, 516718, 536836, 434568, 412274, 575758, 526562, 500773, 505571, 515747, 502620, 580965, 544813, 479097, 519749, 448168, 407114, 529154, 493199, 585653, 536120, 501792, 548170, 607419, 610074, 433500, 439096, 515398, 474545, 567433, 519762, 460292, 468817, 535341, 556812, 465000, 415200, 620888, 572631, 591849, 632980, 509702, 499970, 597086, 550101, 497098, 512413, 425037, 418360, 544922, 496881, 400406, 437322, 532960, 569794, 474838, 463607, 620909, 575462, 625253, 590308, 512915, 561591, 525959, 558528, 533446, 538561, 575831, 608490, 489029, 509020, 609615, 594053, 437913, 418187, 433639, 395150, 399046, 430502, 523903, 568082, 457464, 491538, 531136, 523915, 621027, 572046, 672879, 630613, 551127, 594951, 501509, 542898, 477476, 474726, 482381, 502225, 460180, 501807, 456212, 490101, 425374, 473674, 502642, 555266, 638556, 586310, 492282, 443339, 377580, 410474, 469000, 477737, 578539, 598008, 546796, 500175, 437927, 429536, 519293, 494094, 396101, 433499, 465529, 417525, 581269, 585351, 482324, 525885, 515731, 467530, 556265, 578964, 543382, 593130, 607831, 564232, 464993, 459479, 374171, 327645, 501087, 466282, 464282, 475833, 511376, 487409, 465294, 415979, 462142, 469348, 557261, 575291, 454307, 503746, 601013, 572087, 427504, 436918, 531324, 576415, 551354, 525549, 540016, 534137, 429504, 415480, 377364, 421811, 527250, 563325, 658330, 673447, 458996, 427333, 389692, 368832, 495177, 535502, 442732, 449491, 613815, 575337, 480093, 518573, 554357, 563945, 633116, 583557, 483702, 520132, 460301, 412172}
{506672, 456612, 519224, 568084, 466138, 447207, 389423, 437068, 536195, 493839, 484157, 529336, 583971, 575735, 675734, 722332, 481258, 530017, 589689, 625689, 467608, 503304, 439703, 468489, 428885, 466696, 437090, 426089, 412306, 429656, 515270, 561557, 584368, 534276, 468003, 494193, 573702, 561764, 645649, 598386, 484217, 530157, 492739, 498586, 583702, 599055, 500661, 527482, 504881, 452692, 441060, 455305, 466130, 513001, 561344, 611732, 568531, 591663, 586113, 552329, 544467, 504703, 493405, 542299, 424995, 401978, 319306, 358546, 450739, 435177, 526858, 488223, 527072, 477884, 384051, 346748, 371389, 417064, 435612, 480858, 505448, 555143, 460053, 492269, 558384, 598109, 635282, 656005, 469166, 431995, 528278, 573164, 459742, 462321, 470647, 444365, 552902, 578353, 600903, 634318, 482767, 432531, 333325, 379419, 428502, 407177, 313904, 277956, 426545, 415272, 322538, 330646, 456571, 461445, 436603, 425134, 481365, 440490, 362118, 313176, 617688, 569420, 654040, 669250, 495367, 545491, 593023, 552630, 597500, 558977, 467286, 456586, 450931, 401990, 397785, 417396, 414437, 436667, 473652, 519078, 522851, 505191, 601870, 578609, 536581, 586613, 532283, 518509, 465185, 495585, 390869, 343200, 432404, 476366, 569952, 591361, 523187, 473086, 421050, 464692, 409938, 414791, 422784, 466865, 578992, 530228, 566774, 547344, 556482, 508180, 413239, 364396, 469523, 421125, 329741, 305573, 541573, 571226, 611148, 659066, 490241, 529932, 438580, 392678, 488184, 452135, 430616, 480837, 515749, 484452, 460807, 496171, 361407, 407420, 332274, 320843, 548685, 521168, 435937, 421642}
Returns: {448811.04500796826, 464790.55204519, 605567.0177217956, 588998.3014754966, 667670.892436949, 510620.31511858304, 519684.7469642102, 437539.9749177773, 357969.66993610444, 319861.4557998268, 299130.4103771292, 400718.9943138797, 588193.1379758251, 448297.72592329426, 389017.2778571151, 430160.009805435, 379948.4197981854, 529747.9398647901, 490602.9246750148, 514946.6053363673, 440658.5403914514, 708610.124044811, 537490.2997456733, 733582.3161865928, 431969.83163080306, 537519.6316952587, 589247.6593536629, 661065.9181905573, 651020.8026013122, 582427.0043291275, 590360.1400542812, 499099.04371190787, 440683.99401734414, 366445.16586610395, 374357.05509444216, 441283.2388845725, 459273.6966792748, 528567.553046011, 650174.7937199152, 468928.8814588605, 620355.4579263399, 373478.33293854026, 478875.915209058, 417390.3165535726, 592689.0414988536, 581848.7376944282, 674918.2520692814, 524942.1745495304, 434243.1604521744, 605264.2465824153, 584877.7311645389, 473699.71448389854, 519095.4651152805, 398382.4291277163, 507395.7499820537, 492754.3684443735, 391725.6437466756, 655912.0422556177, 473304.4806522976, 713747.0953733067, 622109.192951431, 501948.5499857614, 436480.1644919313, 427504.8545295157, 399258.3167638085, 520319.3687592655, 612975.3341376232, 657758.4392507874, 650197.6894335235, 461252.72364377056, 551944.831630015, 442641.54599582043, 457028.9219674088, 512930.5277819526, 654750.5103670083, 482827.81227754365, 639699.1526148039, 383967.0180777439, 531045.0002555691, 445166.98365208507, 356696.8358281621, 543160.4403764696, 405693.5641903544, 630334.5225901732, 552148.6155094358, 542353.9741521766, 352321.58056133415, 534037.9592501863, 348163.573110339, 633951.4767242372, 627323.8213489825, 466514.1957878788, 429663.2523902346, 436013.38466908946, 414412.8468308399, 534843.6691484634, 592848.1077593389, 473385.1966184404, 693445.8530286684, 300526.6022508848, 607016.5558448908, 250227.72961622005, 531860.5145577864, 369777.7786933861, 461393.20682546764, 556952.4525703791, 554980.5437639641, 592186.1064365386, 566773.7160587547, 542303.2431857949, 640602.1724646612, 356428.664437863, 547664.8830906952, 319514.43623490975, 450920.1357303095, 457194.2003183025, 647604.7295923157, 493459.48037151084, 665737.36961892, 395117.18344050774, 460794.011302737, 612455.290872017, 491014.6549897723, 414751.69278856984, 392162.8559480487, 399641.3709450521, 365003.8794957229, 625312.7083223722, 550577.8050725363, 699893.6586113787, 587868.2802170397, 607106.695822972, 425767.28840043576, 405059.2509602855, 502557.7915265346, 589729.8188092002, 594893.075450992, 551334.5672461508, 519046.9492565732, 508114.91770860803, 718368.5997275626, 524573.3396718687, 726597.8107091929, 424912.514436374, 632305.2317505354, 515694.1998668158, 439490.23756876413, 568820.257679188, 466053.26647495024, 665227.7547700737, 520710.1121098063, 486739.2285634751, 536187.6510269585, 287339.013445567, 436487.54346800444, 279600.2439869909, 567268.7052101631, 427239.9477290747, 479434.6601197737, 247559.17379079427, 389594.27315063344, 291476.196335989, 504079.5279513372, 479851.9039958051, 569980.1688654665, 291021.01264826366, 475564.7231916958, 258070.692191199, 649650.326297476, 425139.0906978883, 455852.52397135604, 375718.3277174751, 431142.14248114947, 472617.2288805351, 419007.95418550854, 512402.2525259716, 538819.7473121325, 352261.2701767208, 458749.25613750715, 292355.37361340877, 581648.1779129162, 500860.69681551843, 477511.0398945968, 671610.3863770326, 562885.8846753539, 723678.9553861923, 361677.83894580405, 564800.9497488831, 537683.3804141993, 659785.4188605068, 585175.6149700112, 571782.6481263092, 460587.26944406994, 625944.403292721, 529479.9624543984, 438184.45855001337, 435599.9900830445, 403738.1120448491, 636462.3165231822, 354034.4567195178, 436628.6913864479, 345878.3384815806, 432550.6322674794, 445795.1510499477, 401755.30232404626, 459265.0219722061, 584022.5113668732, 541597.6674279327, 625188.8340947366, 450464.06290651916, 532093.3407796058, 464226.599156089, 567751.6583780183, 661022.1387042474, 666149.4281520974, 643192.979905041, 528706.3110714625, 570884.0105730125, 359687.2865077261, 463960.81694542244, 306225.6896939311, 548470.3292272906, 517155.3794019895, 540835.9603144985, 513336.2203100696, 340872.428579758, 413354.4544426993, 342782.0081257179, 452343.50158027216, 414319.4014292316, 400376.58599172713, 607450.0299794775, 496941.9002668501, 633433.4877737501, 451933.18235853757, 542337.5149608542, 623548.982251089, 439633.9744803052, 572197.2120108145, 353826.0745340296, 447026.3484512592, 458981.65071820206, 645883.9301736258, 480327.89609138883, 656557.0528602191, 380899.1052302055, 372550.7419816425, 558926.174978282, 559063.2030459013, 631127.9884441042, 595164.1097788123, 537871.7579119749, 571259.0868492826, 568564.8782539571, 595682.1174091166, 370061.6904249618, 496430.52349461894, 357850.17514504475, 480911.2344419817, 449063.9865388621, 405101.7246670988, 263988.5472507385, 312564.005023037, 301893.30213818, 500811.0789376935, 599089.2597990519, 685046.7254896585, 676917.4458217224, 723960.8185009938, 584799.6225457398, 493505.9897208328, 556578.2442422298, 416017.43790693476, 372199.49183896394, 323828.06170530175, 410943.7677459129, 597066.5529397927, 420156.8513402692, 403645.86072600493, 369280.1786548513, 378207.5243832959, 465990.52476174524, 637171.9772385971, 447679.89895497967, 442530.48495944496, 401694.14590748964, 419537.60843569995, 499014.8920470657, 569004.1417570488, 476317.0945035437, 703333.6802987145, 328142.9568303885, 629246.6114621371, 260978.18755955563, 587316.0538074588, 529736.5610439879, 472193.15299321176, 366192.32327294, 390421.0341076879, 423753.77368006355 }
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolylineCover with a public method vector<double> cover(vector<int> L, vector<int> X, vector<int> Y) · 80 test cases · 2 s / 256 MB per case