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})$).