P2632 Explorer

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

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

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 a single real number on one line: the length of the minimum spanning tree, rounded to three decimal places.

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