#P1396. 电缆建设(cable)

电缆建设(cable)

【问题描述】

教主上电视了,但是蔚蓝城郊区沿河的村庄却因电缆线路老化而在直播的时候停电,这让市长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的村庄的纵坐标。

【输出格式】

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

【样例输入】

2 3 1 3
1 2
2 2 1

【样例输出】

7.24

【样例解释】

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

(1,1)-(1,3)

(1,3)-(3,4)

(3,4)-(3,2)

(3,4)-(3,5)

【数据规模】

对于20%的数据,n,m≤10;

对于40%的数据,n,m≤1000;

对于70%的数据,n,m≤100000;

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