/ Vijos / 题库 /

电缆建设

电缆建设

描述

教主上电视了,但是蔚蓝城郊区沿河的村庄却因电缆线路老化而在直播的时候停电,这让市长SP先生相当的愤怒,他决定重修所有电缆,并改日播放录像,杜绝此类情况再次发生。

河流两旁各有n,m个村庄,每个村庄可以用二维坐标表示,其中河流一旁的村庄横坐标均为x1,河流另一旁的村庄横坐标均为x2。由于地势十分开阔,任意两个村庄可以修建一条电缆连接,长度即为两村庄的距离。要修建若干条电缆,使得任意两个村庄都可以通过若干个有电缆连接的村庄相连。

因为修建的经费与长度成正比,SP市长当然希望所花的钱越少越好,所以他希望你来帮助他设计一套方案,使得电缆总长度最小,并告诉所需要的电缆总长度。

格式

输入格式

输入的第1行为四个正整数,n,m,x1,x2,表示河流两旁的村庄数以及横坐标。

第2行有n个正整数y1[1], y1[2]... y1[n],描述了横坐标为x1的村庄的纵坐标。第1个整数为纵坐标最小的那个村庄的纵坐标,从第2个整数开始,第i个整数代表当前村庄与前一个村庄的纵坐标差,即y[i]-y[i-1]。

第3行有m个正整数y2[1], y2[2]... y2[n],用同样的方法描述了横坐标为x2的村庄的纵坐标。

输出格式

输出仅包括一个实数,为最小的总长度,答案保留两位小数。

样例1

样例输入1

2 3 1 3
1 2
2 2 1

样例输出1

7.24

限制

对于20%的数据,n,m≤10;
对于40%的数据,n,m≤1000;
对于70%的数据,n,m≤100000;
对于100%的数据,n,m≤600000,所有村庄纵坐标不超过10^8,x1<x2<2000,输入文件不超过4M。

时限1s。

提示

按如下方案建设电缆,括号内代表村庄的坐标,“-”代表有电缆连接。

(1,1)-(1,3)
(1,3)-(3,4)
(3,4)-(3,2)
(3,4)-(3,5)

请使用双精度实型进行储存运算。

信息

ID
1466
难度
7
分类
动态规划 | 单调性DP 点击显示
标签
递交数
341
已通过
58
通过率
17%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第2次模拟赛