We have $$$n$$$ squares, $$$s_1, s_2, \dots, s_n$$$, on a 2D plane. Now, we want to draw a square $$$S$$$ such that for each of the existing squares, the intersection with $$$S$$$ is also a square with nonzero area.
Formally, we want to find a new square $$$S$$$ such that for each $$$i \in \{1, 2, \dots, n\}$$$, the intersection $$$S \cap s_i$$$ is also a square with nonzero area.
Print out any valid square $$$S$$$.
The first line contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of squares laid out.
Each of the next $$$n$$$ lines describes a square using four integers $$$x_1, y_1, x_2, y_2$$$, where $$$(x_1, y_1)$$$ is the lower-left corner and $$$(x_2, y_2)$$$ is the upper-right corner. It is guaranteed that $$$x_1 \lt x_2$$$, $$$y_1 \lt y_2$$$, and that the shape described is an axis-aligned square. All coordinates lie within the range $$$[-10^9, 10^9]$$$.
Output the square $$$S$$$ as four integers $$$x_1, y_1, x_2, y_2$$$, denoting its lower-left and upper-right corners. It must satisfy $$$x_1 \lt x_2$$$ and $$$y_1 \lt y_2$$$, and all coordinates must lie within the range $$$[-10^9, 10^9]$$$. The square must be axis-aligned.
3 2 3 4 5 7 3 10 6 8 1 12 5
3 4 9 10
1 1 1 2 2
1 1 2 2
Below is an illustration of the sample test case, where the blue squares are the ones given in the input and the red square is our output.
—
Problem Idea: Alex_C
Problem Preparation: eysbutno
Occurrences: Novice A / Advanced A
