Background

Hint: The testdata for this problem is relatively weak; passing this problem does not guarantee that your program or approach is entirely correct.

Problem Description

Given two straight lines with $n, m$ points on them respectively, find the minimum spanning tree formed by these $n + m$ points.

Input Format

The input consists of $5$ lines.

• The first line contains $n$ and $m$.
• The second line contains four integers $x_a,y_a,x_b,y_b$.
• The third line contains four integers $x_c,y_c,x_d,y_d$.
• The fourth line contains $n$ real numbers, representing $n$ points on the first line. For a point, a real number $t$ indicates that the coordinates of the point are $(t x_a + (1 - t) x_b, t y_a + (1 - t) y_b)$.
• The fifth line contains $m$ real numbers, representing $m$ points on the second line, in the same manner as above.

Output Format

Output a single real number on one line: the length of the minimum spanning tree, rounded to three decimal places.

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

Hint

Constraints: $1 \le n,m \le 100000$, and the absolute values of $x_a,y_a,x_b,y_b,x_c,y_c,x_d,y_d$ are all less than or equal to $10^5$. $0 \le t \le 1$.

2024/2/8: Added one hack testdata.

Translated by ChatGPT 5