19298번 - Number of Cycles 스페셜 저지다국어

문제

Jaehyun likes computational geometry. Here is Jaehyun's question: "We are given $n$ segments on the Cartesian plane. Count the number of simple cycles in the generated graph."

Formally, a set of $n$ segments $S = \{s_1, s_2, \ldots, s_n\}$ generates the following graph $G = (V, E)$.

For a point $v$ of the plane, $v \in V$ if $v$ is one of the endpoints of the segments or $v$ is an intersection of two or more segments.

For two distinct vertices $u$ and $v,ドル $(u, v) \in E$ if there is a segment $s_i \in S$ containing vertices $u$ and $v,ドル and there is no vertex on $s_i$ between $u$ and $v$.

A simple cycle is a cycle with no repeated vertices or edges.

Zigui tried to solve Jaehyun's problem, and he found it is possible to make various answers with just a few segments.

For given $N,ドル find a set of segments such that the number of simple cycles in the graph generated by these segments is $N$.

입력

The first line contains an integer $N$ (1ドル \le N \le 1000$).

출력

The first line of the output must contain an integer $K$: the number of segments (1ドル \le K \le 12$).

Each of the next $K$ lines must contain four integers $x_{1},ドル $y_{1},ドル $x_{2},ドル and $y_{2}$ denoting a segment with endpoints $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ ($-10^{9} \le x_{1}, y_{1}, x_{2}, y_{2} \le 10^{9},ドル $(x_{1}, y_{1}) \neq (x_{2}, y_{2})$).

제한

힌트