P6440 [COCI 2011/2012 #6] REZ【征集SPJ】

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

有一个由蓝莓、草莓和巧克力制成的矩形蛋糕。它的形状类似一个广场，左下角坐标为 $(-5000,-5000)$，右上角坐标为 $(5000,5000)$。（坐标系的单位是毫米）面积为 $100$ 平方米。 专业人员强烈建议用湿刀和干勺子食用这块蛋糕。并且： - 每一刀的起始点都在蛋糕的边上； - 一次切割不能完全切割在蛋糕的边上； - 没有任何两刀有相同的起点和终点；也就是说，所有的切割线都是不同的。 只有在切割完最后一次后才能进行分离和计数。也就是说，在切割蛋糕的过程中，蛋糕始终保持矩形不变。 请你找出：最少要切几刀才能把蛋糕切成至少 $k$ 块？并输出每一刀的起点和终点坐标。

输入一行一个整数 $k$，表示至少把蛋糕切成的块数。

输出第一行为一个整数 $n$，表示最少的刀数。 接下来的 $n$ 行，每行四个整数。分别为这一刀起点的坐标和终点的坐标。 对于蛋糕边上的每个点，保证 $\max(|x|,|y|)=5000$。

#### 数据规模与约定 对于 $100\%$ 的数据，保证 $1\le k\le 10^6$。 #### 说明 **题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T4 REZ***。