Explorer
题目背景
提示:本题数据较水,通过本题不代表程序/做法完全正确。
题目描述
给出两条直线,上面分别有 $n,m$ 个点,求这 $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
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
说明
$n,m \le 100000$,$AX,AY,BX,BY,CX,CY,DX,DY$ 的绝对值均小于等于 $10^5$,$0 \le t \le 1$。
------------
2024/2/8 添加一组 hack 数据。