25726번 - Symmetry: Closure 스페셜 저지다국어

A point set $S$ is symmetric about a line $\ell$ if and only if there exists $s' \in S$ satisfying that $s'$ and $s$ are symmetric about the line $\ell$ for all $s \in S$.

Let us denote the distance between two points $a$ and $b$ as $d(a,b)$. The distance between two non-empty point sets $A$ and $B$ is $\inf \left\{d(a,b) : a \in A, \, b \in B \right\}$. The infimum of a non-empty real number set $S$ is the maximum value of $x$ which satisfies $x \le s$ for all $s \in S$.

Lines $\ell_1, \ell_2, \ldots, \ell_n$ are given, where two or more lines may coincide. For a point $s$, define $C(s)$ as the intersection of all sets $S$ satisfying $s \in S$ such that $S$ is symmetric about $\ell_i$ for all $i = 1, 2, \ldots, n$.

There are $q$ queries. For each query, given two points $A$ and $B$, find the distance between $C(A)$ and $C(B)$.

There are multiple test cases. The first line of input contains an integer $T$ ($1\le T\le 10^5$), the number of test cases. For each test case:

The first line contains an integer $n$ and $q$ ($1\le n, q\le 10^5$): the number of lines and the number of points.

The $i$-th of the following $n$ lines contains four integers $x_{P_i}$, $y_{P_i}$, $x_{Q_i}$, and $y_{Q_i}$: the coordinates of $P_i$ and $Q_i$ such that $\ell_i$ passes through $P_i$ and $Q_i$. It is guaranteed that $x_{P_i} \ne x_{Q_i}$ or $y_{P_i} \ne y_{Q_i}$. Any two lines may coincide.

The $i$-th of the following $q$ lines contains four integers $x_{A_i}$, $y_{A_i}$, $x_{B_i}$, and $y_{B_i}$: the coordinates of $A_i$ and $B_i$.

It is guaranteed that the absolute value of all coordinates in the input does not exceed $10^9$.

It is guaranteed that both the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$.

For each test case:

For each query, output the distance between $C(A)$ and $C(B)$.

The distance you output will be considered correct if the relative error or absolute error to the jury does not exceed $10^{-9}$.