题目描述

给出两条直线，上面分别有n,m个点，求其最小生成树。

输入格式

输入包括5行。 第一行为n和m。 第二行为四个整数AX AY BX BY。 第三行为四个整数CX CY DX DY。 第四行为n个实数，代表在第一条直线上的n个点。对于某个点，用一个实数t来表示该点的坐标为(AX * t + BX * (1 - t), AY * t + BY * (1 - t))。 第五行为m个实数，代表第二条直线上的m个点，表示方法同上。

输出格式

一行一个实数,为其最小生成树长度,四舍五入至三位小数。

4 4 
0 0 10 10 
0 10 10 0 
0.1 0.3 0.6 0.8 
0.1 0.3 0.6 0.8

19.638

提示

30%的数据：n,m <= 1000

100%的数据：n,m <= 100000

AX,AY,BX,BY,CX,CY,DX,DY的绝对值均小于等于100000

0 <= t <= 1