闲话 #9: AGC042D Geometric Geometry 题解

· · 闲话

前言

本题解为非正解。但是建议先阅读本题解，再阅读正解题解。原因稍后会阐述。正式题解链接在本文最下方。

本题是 AGC 十分少见的提交答案题（事实上有一道与这题类似的传统题 ABC316G，但是做法略有不同，并且本题使用传统题做法无法在较短的运行时间限制内完成）。因为是提答，所以考虑乱搞；但考虑到这是 AGC 的黑题，所以大部分人第一时间放弃了乱搞。这里提供一种较为新颖且离奇的做法。

解法

观察到这是一道带 SPJ 的最优化几何构造题，并且混杂了二维计算几何和三维计算几何的知识，这必然需要我们对这些几何知识有较为深刻的了解。因为本人的几何不是很不好，所以在做题前使用了一些工具。这些工具包括但不限于直尺、圆规、GeoGebra、无语泽（@qu_ming_nan，几何大佬）。又由于这道题需要使用 AtCoder 上的 Text (cat) 语言提交，所以我们需要提前熟悉这种语言。经过了解，这款语言的 IDE 十分简洁，叫做记事本。

为方便理解下文的阐述，建议先完成两道较为简单的题目：JOISC2021 Day1 T1 曲芸飛行 (Aerobatics) / AGC301G Worst Picture

只要你做过上面两个题，就会发现这道题的重点并不是几何。使用上面两个题的方法转化题意后，我们发现本题无人机的 3 种指令，在避障时只有一种是有用的（横滚，Roll）。只需执行 360 次该指令即可完成避障、航拍，而另一个参数可使用 mt19937_64 与 uniform_int_distribution<unsigned long long> 在范围 [0,2^{64}) 内均匀随机生成（可以证明这样出错的概率不大于 2^{-256}\times 64=2^{-250}）！但是本题有一个额外的要求：运行若干遍程序，输出应该相同（类似 Codeforces 的 Hack 机制里面不允许 Generator Crash），故不可以用 time(0) 作为随机种子。

答案如下，可以自行编写 SPJ 进行验证。

Roll 17680604849673045180
Roll 11589081325344720931
Roll 6136681978563452351
Roll 16632633540468996387
Roll 16401738831747761123
Roll 13180452634138427846
Roll 14750011169868352720
Roll 198827228445834793
Roll 16516479140784638950
Roll 12601630301485239611
Roll 4481870617215778325
Roll 12889871476887916255
Roll 2909706306284637221
Roll 18175591745621106991
Roll 10199930060208545401
Roll 14806268122737180732
Roll 32688188727603616
Roll 8788236240449444031
Roll 12207390160067758791
Roll 10866306414902191568
Roll 11520018741442173220
Roll 5630165825128910699
Roll 9171649292896289827
Roll 13440859596961611781
Roll 4388530002360020799
Roll 15722121096050325903
Roll 10515615100761602063
Roll 9193590649479759551
Roll 1031331296144158049
Roll 1456287379403043521
Roll 3742754521334331886
Roll 8795737304689501143
Roll 12188033152556092847
Roll 12176738069702324524
Roll 6849597318989748313
Roll 10112810723066042407
Roll 1361928815129053387
Roll 5362860811694239104
Roll 8642409068359100093
Roll 15460957535766264981
Roll 2423740603225454721
Roll 6630504099607967104
Roll 16027699420589209706
Roll 2719336304897851378
Roll 13389071506883028196
Roll 6623906077489487390
Roll 1320540245244662008
Roll 10158180429919812187
Roll 14497429761817191314
Roll 17975413647436675015
Roll 3700153093340083715
Roll 782974879971489679
Roll 12870568096037667617
Roll 17484597811057941722
Roll 3643874951011400115
Roll 15429945149079189792
Roll 4755462023294735095
Roll 2228446652100538638
Roll 16039285217207478020
Roll 10399508297643585382
Roll 16808031696151491946
Roll 11341248775646932000
Roll 8516994975646695085
Roll 1731009244064088097
Roll 18109979363005571411
Roll 4119111462116750967
Roll 3506487900806704653
Roll 7848662335326768504
Roll 4964983454247031334
Roll 7354031886400271559
Roll 4546388530370832264
Roll 9225996442872588275
Roll 13621224183975841431
Roll 3935451603223642740
Roll 8929289993168084129
Roll 11194747749761523798
Roll 9178511108483932547
Roll 4003049427961128047
Roll 8476165692365592125
Roll 17654259002487873965
Roll 3635994434376998921
Roll 4804203269458202042
Roll 16146794772856400952
Roll 4097928945004593985
Roll 17889325381999874228
Roll 10501417165896924519
Roll 14167534224686613567
Roll 2172639726047718700
Roll 7281759468959273799
Roll 1346711398404548279
Roll 1107622444234812208
Roll 6905754421917444247
Roll 17048858289807811224
Roll 15853697012060600289
Roll 4147768812526822749
Roll 9665799491395380583
Roll 2303450950866123203
Roll 3614919893420692980
Roll 10297309773923999297
Roll 11670870062679906169
Roll 10199762440014498405
Roll 3088201292660946057
Roll 9777066784309470697
Roll 2160440523853779765
Roll 6536650391201522768
Roll 13696417680927537793
Roll 7935113541011575813
Roll 3610609434163779090
Roll 13821128894940110793
Roll 3997787394417160637
Roll 4247022744444217699
Roll 110727084340665229
Roll 2529079517559902651
Roll 11564165091172762424
Roll 6760645546199686734
Roll 18008654323722878797
Roll 9127964080987039518
Roll 2761051558635976890
Roll 10943827231384461841
Roll 5170995080920649574
Roll 12116120441721335710
Roll 13945269739776494735
Roll 8097790034991026214
Roll 8494959006187829938
Roll 8761220285422290685
Roll 3419452108550486523
Roll 2180299346832064024
Roll 11405437440496417998
Roll 6948664386951150828
Roll 6468443896771795335
Roll 15969805215352173850
Roll 12846831137691943414
Roll 1462273459039318775
Roll 15006387893391309475
Roll 5149338946153018934
Roll 11564827814895031501
Roll 1481864572356362688
Roll 15458270481394818161
Roll 11310974889630273167
Roll 6667880204265795950
Roll 4962373599428405806
Roll 2473217848839152085
Roll 9781958025446911948
Roll 15603699908823154468
Roll 8089811978689959959
Roll 14045380729980775947
Roll 13306413259117593627
Roll 5818123401696131583
Roll 16672890877633096360
Roll 5026437883268868701
Roll 3995102341267904732
Roll 4296270335699692512
Roll 3251571789387404350
Roll 11925010605817112939
Roll 3824941355660312338
Roll 7729083613943704683
Roll 12279466705536699995
Roll 17298737062783106243
Roll 13428734309913544679
Roll 2015589165544167291
Roll 4627793208671385619
Roll 17234790574808729837
Roll 9068233260784942140
Roll 12825090242008046372
Roll 16767594052305037595
Roll 4536084511380676527
Roll 10462430866627132228
Roll 6241872008130168328
Roll 5668769969592270326
Roll 9420622025847701666
Roll 7463593234002542415
Roll 1882002429305941536
Roll 15305842526391640924
Roll 1523885304163652681
Roll 4906200638309212664
Roll 1130816431483579534
Roll 10631061744812583877
Roll 4491352461480183078
Roll 16839353515721412500
Roll 5362994355616782449
Roll 5417566960714589105
Roll 15816784539667494621
Roll 4556863171135993536
Roll 5504908629892416195
Roll 12051081697538745823
Roll 4858151205453098452
Roll 10795896685370618003
Roll 992577602393037080
Roll 9449661247695913675
Roll 2747813826823034136
Roll 13467661242223452256
Roll 9193499472185259666
Roll 4851112518109365355
Roll 13972279620453612914
Roll 1729884366766704202
Roll 15029997099330369833
Roll 16013827640350361822
Roll 16400653218060151127
Roll 4237424055772262009
Roll 17413485018183953416
Roll 3929002908345688541
Roll 17224619542968270997
Roll 14662357425339001025
Roll 7787185383333397639
Roll 4642951747588515390
Roll 11289917015733716455
Roll 5557152713664221812
Roll 10544942907365892505
Roll 5735735196144694444
Roll 843645675310851565
Roll 7617676318433097451
Roll 17180405414201028755
Roll 12261475528430797136
Roll 7445195563304970843
Roll 13473758167428517961
Roll 1972624353452481780
Roll 5472262237222354241
Roll 17558212646549652238
Roll 3198695526791267309
Roll 10190031667446901466
Roll 17425198853526740123
Roll 8803277801624516728
Roll 9847622485179253293
Roll 12606939855461599662
Roll 3807825827490820521
Roll 1902997500755156181
Roll 5761811931395896377
Roll 2166153734708986289
Roll 11019431122533284230
Roll 4024269502398831516
Roll 16447959789828490628
Roll 2628235396995388609
Rick 14044629012579674362
Roll 5648706692213802007
Roll 10322390549474685202
Roll 8702507867660387904
Roll 16252969579240425811
Roll 14684257333710254536
Roll 14908310705644129665
Roll 18332313922047523468
Roll 3056079804978580082
Roll 14226168366276600058
Roll 4507082429222353685
Roll 11150972254258863039
Roll 14883904677046461286
Roll 5023751897133083831
Roll 2993610167184680572
Roll 12719583580781653139
Roll 4925295037517826127
Roll 11741752212253868159
Roll 6087676105391479911
Roll 6326415869543319840
Roll 747746758295810510
Roll 3590226898932691321
Roll 4796781706663725874
Roll 8837279638644088117
Roll 1825871208651415013
Roll 11744404963860982381
Roll 9063664921696210255
Roll 9537028207328248396
Roll 11419374602126012595
Roll 2946182803155571192
Roll 18019363957986657569
Roll 16632946567777972374
Roll 11562140002288834007
Roll 14399746907654258922
Roll 17115764353785469985
Roll 5237010597995307652
Roll 9134087453153123128
Roll 14384265709664685562
Roll 17186048322707829193
Roll 13959230667236577123
Roll 14442929778088855040
Roll 192610545635685075
Roll 9728881908707285572
Roll 10205669313343981594
Roll 160911189119349426
Roll 5924879147514361956
Roll 12065643578609253430
Roll 11140719729252436655
Roll 4930335621201709899
Roll 9911919012914647656
Rick 17694483408450085160
Roll 10775769526249859535
Roll 15978178944377823203
Roll 2763257839145275513
Roll 16893004207606647897
Roll 1977533037198565016
Roll 15487209945005887115
Roll 17083552415765431671
Roll 811634089664894168
Roll 9907157034524598241
Roll 5064494951777422508
Roll 9885274211661655123
Roll 6418207486243170694
Roll 7358967300383173853
Roll 9603525427700585152
Roll 15842526677854473
Roll 8660948431739203317
Roll 4178327514595843414
Roll 12856669068790535710
Roll 14621155872007622152
Roll 13608523912047697
Roll 5660847987239711462
Roll 11492584001851749141
Roll 3168091424312990457
Roll 7143873189182812890
Roll 1198803021464664706
Roll 335969433126854115
Roll 7645231931210393264
Roll 4949145473830107913
Roll 15875723223293682605
Roll 11766419348950197063
Roll 9913159991391222725
Roll 14886504185318272535
Roll 1411868828790921782
Roll 337481173969448264
Roll 9425586973909721234
Roll 4264889629654988666
Roll 15582971602814410058
Roll 16620360467519671473
Roll 15520589784612023219
Roll 1894044257323429573
Roll 11095494729711107748
Roll 8344188469001551309
Roll 16960086806817974626
Roll 2403530504857947
Roll 15451139327813532975
Roll 15895810586467989775
Roll 9507683422404479644
Roll 12845916363495403539
Roll 599811654114691712
Roll 8887962346564936937
Roll 12116337704435594207
Roll 4646128527791220851
Roll 17905951334102412127
Roll 15974655894539191837
Roll 4785161086479147035
Roll 5147180302961079778
Roll 5806491206914185218
Roll 14836528431632532388
Roll 6977026209863055776
Roll 3942678056917821710
Roll 13532175106449926143
Roll 2220259196732384035
Roll 18317701151688851128
Roll 16948605752681069967
Roll 3773019897797782772
Roll 16207994495533735511
Roll 7306541090461391795
Roll 16987975409669006484
Roll 16484579441569505972
Roll 1808684087775289646
Roll 11967571264970432240
Roll 16167519438627949930
Roll 18026181637312951031
Roll 11917752692665682332
Roll 4698408219178747094
Rick 1430278775090136618
Roll 10004918263662946525

于是，我们通过了此题。个毛线。

AGC 没有 042。ABC 也没有 316。菜，就多练。