P15838 [Lanqiao Cup 1st International Contest] Planar Coloring

Xiao C has a very large sheet of white paper (assume it is infinite). In his spare time, Xiao C likes to draw various patterns on the paper using straight lines. These lines divide the white paper into several regions. Xiao C wants to fill each region with one of two colors: black and white. If two regions share a common edge, then they are adjacent. If two adjacent regions are filled with the same color, the coloring will look very unattractive. Also, Xiao C wants to keep the center of the paper in its original white color, i.e., the region containing the origin is white. Now Xiao C has already drawn these $n$ lines, but there are too many regions after splitting, and he cannot find a good-looking coloring plan. Xiao C hopes that you, being clever, can tell him a coloring plan. Xiao C will ask you for the colors of $m$ points on the paper to help him understand the coloring. If the coloring plan is not unique, you only need to give one.

The first line contains two positive integers $n, m$, representing the number of lines and the number of queried points. The next $n$ lines each contain $4$ integers $x_1, y_1, x_2, y_2$, describing a line passing through the points $(x_1, y_1)$ and $(x_2, y_2)$. The next $m$ lines each contain $2$ integers $q_x, q_y$, representing the color query for the point $(q_x, q_y)$.

If no good-looking coloring plan exists, output $-1$. If a good-looking coloring plan exists, output $m$ lines, each containing one number ($0$ or $1$), representing the color of the queried point in your coloring plan ($0$ means black, $1$ means white).

### Constraints and Notes on Test Cases For $30\%$ of the test cases, $1 \le n, m \le 1000$, and each line is guaranteed to be parallel to the coordinate axes. For $50\%$ of the test cases, $1 \le n, m \le 10^5$, and each line is guaranteed to be parallel to the coordinate axes. For the remaining $20\%$ of the test cases, $1 \le n, m \le 1000$. For all test cases, $1 \le n, m \le 10^5$, and $0 \le |x_i|, |y_i|, |q_x|, |q_y| \le 10^8$. For all test cases, it is guaranteed that the point $(x_1, y_1)$ is different from the point $(x_2, y_2)$, all given lines are pairwise distinct, $(q_x, q_y)$ is not on any given line, and the origin is not on any given line. Translated by ChatGPT 5