28004번 - LaLa and Magic Circle (LiLi Version) 스페셜 저지다국어

문제

This is an output-only problem.

$\color{blue}{\text{LaLa}}$ has a pile of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circles in her laboratory.

A $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle can be represented as a simple polygon drawn with special ink, and is usable if it is convex. i.e. all of its internal angles are equal or less than $\pi$.

$\color{blue}{\text{LaLa}}$ plans to turn every $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle into a usable one. However, they may lose all their $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$al power if done incorrectly. Thankfully, $\color{blue}{\text{LaLa}}$ has the perfect $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$al tool for that.

The tool works as follows. When you toss in a $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle, if the circle is usable, the tool reports that it is. Otherwise, it takes two distinct points $u$ and $v$ such that

• $u$ and $v$ lie on the boundary of the convex hull of the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle, and
• none of the points on the path from $u$ to $v$ through the boundary of the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle in counterclockwise order lie on the boundary of the convex hull of the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle, except for $u$ and $v$.

Then, it rotates the $u$-$v$ path by $\pi$ around the midpoint of $u$ and $v$. In other words, for each point $w$ on the $u$-$v$ path, $w$ becomes $u+v-w$ where the addition is done coordinate-wise over the two dimensional coordinate system over the paper the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle is drawn on. Note that the result of this modification is also a simple polygon.

Little did $\color{blue}{\text{LaLa}}$ know, $\color{blue}{\text{LaLa}}$'s sister, $\color{purple}{\text{LiLi}},ドル overheard $\color{blue}{\text{LaLa}}$'s plan. Knowing how lazy $\color{blue}{\text{LaLa}}$ is, as a prank, $\color{purple}{\text{LiLi}}$ will sneak in a $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle that takes large amount of applications of the tool to make it usable. More specifically, $\color{purple}{\text{LiLi}}$ will add a $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle to the pile which is a union of equal or less than 1ドル,000円$ line segments and the tool can perform some sequence of modifications with between 120ドル,000円$ and 1ドル,000円,000円$ steps that turns it circle into a usable $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle.

Write a program to help $\color{purple}{\text{LiLi}}$ compute one such magic circle.

입력

출력

The output should be in the following format:

$N$

$x_0$ $y_0$

$x_1$ $y_1$

$\vdots$

$x_{N-1}$ $y_{N-1}$

$Q$

$a_0$ $b_0$ $c_0$ $d_0$

$a_1$ $b_1$ $c_1$ $d_1$

$\vdots$

$a_{Q-1}$ $b_{Q-1}$ $c_{Q-1}$ $d_{Q-1}$

where the initial $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle is the union of $N$ line segments connecting points $(x_i, y_i)$ and $(x_{(i+1 \bmod N)}, y_{(i+1 \bmod N)})$ for all integers 0ドル \le i < N,ドル and it has a sequence of modifications by the tool of length $Q$ such that $i$-th modification choose the counterclockwise path from point $(a_i, b_i)$ to $(c_i, d_i)$.

The output should satisfy the following constraints:

• All the numbers in the output are integers.
• 3ドル \le N \le 1,000円$
• 120ドル,000円 \le Q \le 1,000円,000円$
• 0ドル \le x_i, y_i, a_j, b_j, c_j, d_j \le 1,000円,000円,000円$ for all integers 0ドル \le i < N$ and 0ドル \le j < Q$.
• $x_i \ne x_j$ or $y_i \ne y_j$ for all integers 0ドル \le i < j < N$.
• $a_i \ne c_i$ or $b_i \ne d_i$ for all integers 0ドル \le i < Q$.
• The sequence of points $(x_0, y_0), (x_1, y_1), \cdots, (x_{N-1}, y_{N-1})$ defines a counterclockwise traversal of the boundary of a simple polygon.
• Choosing the counterclockwise path from $(a_i, b_i)$ to $(c_i, d_i)$ for the modification on the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle after the first $i$ modifications is valid for all integers 0ドル \le i < Q$.
• The final $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle is usable.

Note that it's allowed to have two consecutive segments meeting at the angle $\pi$. Also note that it is not required to minimize any number, your program just have to satisfy all the output constraints.

제한

노트

Please note that the sample output above does not satisfy the condition 120ドル,000円 \le Q \le 1,000円,000円,ドル thus it will give Wrong Answer verdict upon submission. It is there only to present the output format.

The following illustrates the initial $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ circle for the sample output.

The following illustrates the sequence of usage of the tool to make it usable. The dotted part of the boundary is the path modified by the tool, which becomes the red part after the modification.