Explorer

题目描述

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

输入格式

输入包括 $5$ 行。

第一行，两个整数 $n$ 和 $m$。

第二行，四个整数 $Ax,Ay,Bx,By$。

第三行，四个整数 $Cx,Cy,Dx,Dy$。

第四行为 $n$ 个实数，代表在第一条直线上的 $n$ 个点。对于某个点，用一个实数 $t$ 来表示该点的坐标为 $(Ax\times t+Bx\times (1-t),Ay\times t+By\times (1-t))$。

第五行为 $m$ 个实数，代表第二条直线上的 $m$ 个点，表示方法同上。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

19.638

提示

对于 $30\%$ 的数据，$n,m\le 1000$。

对于 $100\%$ 的数据，$n,m\le 10^5,0\le t\le1,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy$ 的绝对值均 $\le 10^5$。

源代码

# Explorer

## 题目描述

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

## 输入格式

输入包括 $5$ 行。 

第一行，两个整数 $n$ 和 $m$。

第二行，四个整数 $Ax,Ay,Bx,By$。

第三行，四个整数 $Cx,Cy,Dx,Dy$。

第四行为 $n$ 个实数，代表在第一条直线上的 $n$ 个点。对于某个点，用一个实数 $t$ 来表示该点的坐标为 $(Ax\times t+Bx\times (1-t),Ay\times t+By\times (1-t))$。

第五行为 $m$ 个实数，代表第二条直线上的 $m$ 个点，表示方法同上。

## 输出格式

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

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

19.638

## 提示

对于 $30\%$ 的数据，$n,m\le 1000$。

对于 $100\%$ 的数据，$n,m\le 10^5,0\le t\le1,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy$ 的绝对值均 $\le 10^5$。