#1784. 傅里叶与交通规划
傅里叶与交通规划
傅里叶与交通规划
题目描述
标题: 傅里叶与交通规划 - Problem - QOJ.ac
2023-2024 集训队互测 Round 2 (Oct 29, 2023)
C. 傅里叶与交通规划
题目背景
傅里叶荣升巴黎市交通部长。新官上任三把火,傅里叶决定重构巴黎市的交通系统。
题目描述
巴黎市的地图可以看成一个无限大的二维平面。傅里叶在上面修建了 n 条传送带:第 i 条传送带修建于 x∈[pi−1,pi),y∈R 的区域中。对于 x<p0 或者 x≥pn 的部分,傅里叶没有修建传送带。
当一个人处于第 i 个传送带的区域内时,他会受传送带影响强制以 vi 单位长度每秒的速度向 y 坐标增加的方向移动。vi 可能为负,此时其 y 坐标会以相应的速度减小。
在位于未修建传送带的区域上时,y 坐标不会受到传送带的影响。
除了受传送带带动以外,这个人自己也可以移动。为了避免在速度不同的传送带间移动时出现跌倒事故,傅里叶委托麦克斯韦设计了脚底附有钢板的鞋子,并且在传送带上安装了强力磁铁。穿上这种鞋子后,你将只能 沿着与某条坐标轴平行,可能与坐标轴同向或反向 的方向,以不超过 V 单位长度每秒的速度移动。有了这种鞋子,在从一个传送带移动到另一个传送带时,先前的速度不会被继承,这个人将立刻按照新传送带的移动速度来移动。(自然,自身的移动还是可以同步进行的)
个人的运动与传送带的运动是叠加的。
在任意时刻,这个人都可以自由调整其运动的速率、方向;可以通过不断在极小间隔内切换方向以达到近似斜向移动的效果,甚至动态调整速率、方向达成近似曲线运动的效果;但是其任意时刻都只能有平行于坐标轴、不超过 V 的瞬时速率。
就算在没有铺设传送带的位置上,这个人仍然可以靠他的自由意志移动,不过还是只能沿坐标轴方向以不超过 V 单位长度每秒移动。(问就是麦克斯韦的靴子已经成为概念级装备了)
现在,傅里叶想知道他的交通系统究竟有多么伟大。因此,他向你提出了 q 组询问,每次询问如果有一个人要从 (x1,y1) 走到 (x2,y2),最少需要多少时间。因为傅里叶是唯一真神,所以他当然不会设计一个有缺陷的交通系统,因此所有的 vi 均严格小于 V,进而总是可以从一个位置走到另一处。(虽然这将会导致就算在最优情况下,通过传送带系统到达目的地的时间也无法小于原本的一半,更多的时候反倒更慢了,但是谁让他是交通部长,而你只是他手下的一个雇员呢?)
输入格式
第一行三个整数 n,q,V,表示传送带数目、询问个数以及人的移动速度。
下一行 n+1 个整数 p0,p1,…,pn,表示传送带的边界信息。
下一行 n 个整数 v1,v2,…,vn,表示每个传送带的速率。
接下来 q 行,每行四个整数 x1,y1,x2,y2,表示此次询问的起讫点。
输出格式
对于每次询问,输出一行一个实数,表示此次移动所需的最小时长,单位为秒。你需要保证输出与标准答案的相对或绝对误差不超过 10−5。
- 如果你怀疑你的代码中出现了较大的精度误差,可以尝试使用更多整数和分数以规避浮点数运算,从而减少误差。
样例数据
样例 1 输入
1 2 10
-5 5
5
-10 -20 10 20
10 20 -10 -20
样例 1 输出
4.3333333333
6.5
样例 1 解释
第一问中,上图是一种极优的行走方式。蓝色区域是传送带所在区域,在其上时我们以 (3,12) 每秒的速度移动(其中自身移动的速度是 (3,7),也即可以看作是三成时间沿着 x 轴正方向、七成时间沿着 y 轴正方向移动;在极短时间内不停切换,可以达成如上图中斜线行走的效果;(3,7) 的自身行走与 (0,5) 的传送带运转叠加成为 (3,12) 的速度向量)。
第二问中,上图是一种极优的行走方案。
需要注意的是,这两问中能达成最少时间的行走方案不止图中给出的两种。
样例 2 输入
1 4 10
-5 5
5
10 -10 10 10
10 10 10 -10
10 -50 10 50
10 50 10 -50
样例 2 输出
2
2
7.6666666667
10
样例 3 输入
5 5 10
-10 -5 0 5 10 15
9 -4 7 -6 2
-1 0 -9 -100
-7 0 7 10
9 0 -3 20
12 0 -17 -30
2 0 19 39
样例 3 输出
8.085714
1.815789
2.382353
4.987500
3.988235
样例 4~5
见下发数据。
数据范围
对于所有数据,均满足 n,q≤1.5×105,−5×105≤p0<p1<p2<⋯<pn≤5×105,|x1|,|y1|,|x2|,|y2|≤5×105,0≤|vi|<V≤5×105。
Subtask 1(5%): 保证 n=0。
Subtask 2(10%): 保证 n,q≤1000。
Subtask 3(10%): 保证对于所有询问,x1=p0,x2=pn。
Subtask 4(10%): 保证所有询问的 x1 全都相等,所有询问的 x2 全都相等(但不保证 x1=x2)。
Subtask 5(15%): 保证 vi 单调不降,且询问的 x1≤x2。
Subtask 6(15%): 保证存在 i 使得 pi=x1=x2。(但并不保证所有询问的 i 都相同)
Subtask 7(15%): 保证除 n,q,V 外,其它值都在合法范围内独立随机得到(p 的随机方式是随机 n+1 个不等的 [−5×105,5×105] 中的值并排序)。
Subtask 8(10%): 保证 n,q≤5×104。
Subtask 9(10%): 无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
100 100 16486
-15826 -15401 -15263 -15097 -14332 -13960 -13522 -13385 -12943 -12823 -12684 -12304 -11985 -11794 -11599 -11053 -10749 -10304 -10242 -9719 -9033 -8317 -8144 -8124 -7951 -7679 -7313 -6846 -5646 -5634 -5204 -4948 -4764 -4502 -3980 -3649 -3431 -3220 -2772 -2658 -2119 -1764 -1550 -1127 -180 -152 -16 831 1083 1192 1469 2197 2467 2475 2510 2574 3169 3301 3410 3537 3698 3908 4012 4100 4188 4440 4747 4764 4937 5577 6063 6516 7896 8174 8721 9103 9196 9699 10049 10201 10789 11087 11109 11224 11286 11604 12286 12633 12697 12734 13290 13524 13590 13657 13836 14065 14856 14937 15632 15817 15911
-15183 -16091 -4831 -14846 -14976 5318 10566 -13233 6013 -9155 15389 2883 -7066 -5689 -4477 -11866 -4113 14669 4757 -6244 -8445 15654 1651 -11359 3090 -2571 9976 -9515 -2414 9224 2029 -11105 -14967 11009 5435 10869 -6603 -8493 -1516 -12321 6373 8643 -15455 -11044 10331 -3813 -11244 -1136 8634 -8338 -3127 -8353 6933 15502 15045 -14370 -6882 1804 -10647 -936 8973 -350 174 16066 -7088 10390 4112 -13060 -9569 -13902 6694 -14110 7571 -4022 7050 -6173 14116 7796 -12532 -7830 -4002 1406 9833 3473 -332 7649 -6781 -704 1553 9924 11173 -5442 -1117 -13998 -4803 -7593 5125 -2718 2595 1443
13473 -6089 -12785 -11081
9272 -6325 1518 2085
5043 -16154 -19031 14824
6473 13406 11609 -5489
3852 -2502 19599 6025
15245 -17619 15038 16572
14909 -4243 4162 -9662
16304 -15387 4428 -7255
12984 5164 -14885 -6136
-16133 -12481 -8756 -16106
3034 17130 2263 17440
17145 -10634 16808 -18355
7347 -930 13973 -4785
7399 -13424 7416 -7317
-15840 -14837 4177 14360
-11868 -8616 -3513 12884
15355 6643 17530 -13992
15028 18004 16698 -8482
9620 206 -6903 -17374
19724 143 16282 3470
4383 17156 13937 -7010
11256 -10518 -17509 -18455
-5250 -15980 15066 -11309
18720 -16521 -5828 -3110
13437 7515 3661 9227
-8037 -2885 7353 7395
-5864 -4097 -14176 -16798
-2568 -6631 10371 -18067
7268 1105 18805 -2513
-12114 4275 -15323 -10790
11669 -9885 -17015 4971
10528 6352 -14964 2980
497 -4652 -5595 7675
-157 1469 8193 -2105
14036 5645 5004 3107
18551 5085 -17151 13766
10848 19311 -2136 -8886
14534 -18511 14451 -5836
19749 12010 -18245 18932
-17922 936 -1597 17948
3131 13328 -9168 9445
434 1889 -10236 -2359
6334 -1614 -16098 -13437
8151 -7836 18215 -18059
3440 11179 -8824 7628
5508 9119 11491 8447
3257 -49 9287 13177
-6714 8369 -19723 -5014
1297 8036 7299 -17730
-13380 9107 1100 8415
-10708 -16516 8876 1284
-10909 4260 -847 9440
8919 12117 -19062 -15681
4348 -15411 15503 -17043
-2670 2681 12139 -13595
17057 -17397 -19755 -3966
-9240 6627 14336 11716
5455 -19793 4646 -12937
-8818 5575 18377 -19729
-6857 -4555 93 14918
-18351 -12774 6281 10564
693 -5599 -3284 10263
-19012 1887 -19689 -13432
-4598 -8804 -899 -7645
-82 789 11312 18403
-12339 -2331 6172 -9987
14915 -435 9244 8067
12848 3474 -14492 18546
664 132 4842 -16606
16049 -1689 -9296 3927
-8545 -14313 -14901 15749
13593 -2289 11038 -14955
15622 -3710 8923 -16590
-17024 7274 -12707 -16875
-18648 -2013 -13307 15519
13550 -2611 17904 -6533
8376 -4617 10745 -13660
-8261 508 -6864 -15387
14009 8462 -18995 14669
19169 1223 -889 16810
16980 10089 17732 2397
-9196 17155 -11847 -12579
-10749 -4114 8299 -16277
-2196 16538 -4912 -14923
6540 18049 7034 3080
1668 9674 -19442 15044
4881 -2722 9115 -9515
-8281 -5230 -8168 15907
-14157 11147 -11372 1896
-5175 7272 1841 10321
12727 5640 -18085 -6661
-7965 -7971 4900 11423
10153 5986 6316 -15103
13701 2568 1296 -6838
9024 10407 -11530 12461
11197 4231 -1857 -4788
19921 -8917 13509 -8080
-3773 3886 -5932 19286
-15131 -10245 -15590 -4446
2216 -9000 13846 7100
1.615883
0.798227
2.571744
0.901895
1.259393
1.477067
0.783341
1.031450
1.872045
0.492039
0.069264
0.488778
0.537998
0.347877
2.267918
1.204079
0.961699
1.085102
1.417229
0.410591
1.338203
1.786142
1.497910
2.021506
0.666832
1.377218
0.868600
1.025575
0.811447
0.629306
2.397819
1.620165
0.868199
0.523671
0.598797
2.634549
1.556498
0.607708
2.719540
1.605444
0.769139
0.712354
1.545173
0.952970
0.758579
0.377418
0.818895
1.133890
1.133104
0.949843
1.887797
0.820326
2.340572
0.682970
1.290099
2.847799
1.719723
0.317930
2.302689
1.194341
2.390281
0.905393
0.911297
0.285227
1.318837
1.223530
0.613912
2.281997
0.769272
1.852824
1.376658
0.601279
0.836044
0.949494
1.015027
0.371346
0.464521
0.664897
2.381602
1.796639
0.512192
1.189792
1.381037
1.152054
0.505393
1.587477
0.424272
0.661170
0.458570
0.609392
2.049600
1.461258
0.906981
1.004950
1.471988
0.957437
0.442742
0.685232
0.455667
1.246041