P7216 [JOISC 2020] Delicious Delicious Hamburger

JOISC2020 Day 1 T2

There is a $10^9 \times 10^9$ metal grid, where $(x,y)$ denotes the cell in the $x$-th column from left to right and the $y$-th row from top to bottom ($1\leq x,y\leq 10^9$). On this grid, there are $N$ hamburger patties, numbered $1,\cdots,N$. The $i$-th patty is placed inside the rectangular region with bottom-left corner $(L_i,D_i)$ and top-right corner $(R_i,U_i)$. Patties may overlap. You need to check whether all patties are cooked. You may choose $K$ cells on the metal grid and insert a bamboo skewer vertically through the center of each chosen cell. For each patty, you can confirm whether it is cooked by inserting a skewer into a cell that the patty occupies. Of course, you may insert multiple skewers into the same cell, or insert skewers into cells with no patty, although that is unnecessary. Formally, you need to find $K$ points $(x_1,y_1),\cdots,(x_k,y_k)$ that satisfy the following conditions: - For every $i$, there exists a $j$ such that $L_i\leq x_j\leq R_i$ and $D_i\leq y_j\leq U_i$. - For every $j$, $1\leq x_j,y_j\leq 10^9$. You need to write a program to output these $K$ points $(x_j,y_j)$. The testdata guarantees that a solution exists.

The first line contains two integers $N,K$, as described above. The next $N$ lines each contain four integers $L_i,D_i,R_i,U_i$, describing one hamburger patty.

Output $K$ lines, each containing two integers $x_j$ and $y_j$. If there are multiple solutions, you may output any one.

#### Explanation of Sample 1 Inserting a bamboo skewer at $(2,2)$ can confirm whether the first two patties are cooked, and inserting a bamboo skewer at $(7,4)$ can confirm whether the last two patties are cooked. Another feasible solution is to insert bamboo skewers at $(3,3)$ and $(6,4)$. #### Subtasks | Subtask ID | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $N\leq 2000,K=1$ | $1$ | | $2$ | $N\leq 2000,K=2$ | $1$ | | $3$ | $N\leq 2000,K=3$ | $3$ | | $4$ | $N\leq 2000,K=4$ | $6$ | | $5$ | $K=1$ | $1$ | | $6$ | $K=2$ | $3$ | | $7$ | $K=3$ | $6$ | | $8$ | $K=4$ | $79$ | For $100\%$ of the testdata, $1\leq N\leq 2\times 10^5$, $1\leq K\leq 4$, $1\leq L_i\leq R_i\leq 10^9$, and $1\leq D_i\leq U_i\leq 10^9$. The testdata guarantees that a solution exists. Translated by ChatGPT 5