P6440 [COCI 2011/2012 #6] REZ [Seeking SPJ]

## 本题征集SPJ，有意提供者可发帖并@题目提供者或私信。

There is a rectangular cake made of blueberries, strawberries, and chocolate. Its shape is like a square: the bottom-left corner is at $(-5000,-5000)$ and the top-right corner is at $(5000,5000)$ (the unit of the coordinate system is millimeters). Its area is $100$ square meters. Professionals strongly recommend eating this cake with a wet knife and a dry spoon. Also: - The starting point of each cut is on the boundary of the cake. - A single cut cannot lie entirely on the boundary of the cake. - No two cuts have the same start point and end point; that is, all cutting segments are different. You may separate and count the pieces only after the last cut is made. In other words, during the cutting process, the cake always remains a rectangle. Find the minimum number of cuts needed to cut the cake into at least $k$ pieces, and output the coordinates of the start and end points of each cut.

One line with one integer $k$, meaning the cake must be cut into at least $k$ pieces.

The first line contains one integer $n$, the minimum number of cuts. The next $n$ lines each contain four integers: the coordinates of the start point and the end point of this cut. For every point on the boundary of the cake, it is guaranteed that $\max(|x|,|y|)=5000$.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1\le k\le 10^6$. #### Notes **This problem is translated from [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T4 REZ***. Translated by ChatGPT 5