1 sekun\(da / 1024\) M\(iB / 100\) points
Mirko recently read about Pick’s theorem that says the following: in the coordinate system, if we draw
a polygon whose vertices are points with integer coordinates, and if \(A\) denotes its area, \(i\) the number
of points with integer coordinates located inside the polygon, and \(b\) the number of points with integer
coordinates located on its edges (including the polygon’s vertices), then it always holds:
\(A = i\) + ^{b}
2 ^{−}}^{.
In order to test the theorem, Mirko used his smart board to create a polygon from magnetic sticks that
have, during the night, sunk to the bottom of the board because due to gravity. Now, Mirko wants to
construct a polygon of the minimal possible area while using all the sticks he found. Mirko can move the
sticks anywhere on his board, but he must not rotate them. Mirko is equipped with the following:
• \(a\) horizontal sticks of length 1,
• \(b\) vertical sticks of length 1,
• \(c\) diagonal sticks of length
√
2 that form a \(45^{◦}\)angle with the positive part of \(x-ax\)is,
• \(d\) diagonal sticks of length
√
2 that form a \(135^{◦}\)angle with the positive part of \(x-ax\)is.
Figure 2: For the polygon above: \(A = 8\), \(i = 4\), \(b = 10\).
a
b
c
d
Figure 3: The sticks Mirko is equipped with.
Determine the polygon of the minimal possible area that can be obtained so that all the sticks are used.
You can assume that the input data is such that it is possible to construct at least one such polygon.
Also, it is possible to score partial points if, using all of the given sticks, you construct a valid polygon
(that is not necessarily of the minimal possible area). For more details, consult the section “Scoring”.

Subtask 1 (5 points): \(c = d = 0\)

Subtask 2 (5 points): \(a = b = 0\)

Subtask 3 (10 points): \(a + b + c + d \le 6\)

Subtask 4 (10 points): \(a + b + c + d \le 20\)

Subtask 5 (10 points): \(a + b + c + d \le 40\)

Subtask 6 (10 points): \(a + b + c + d \le 80\)

Subtask 7 (10 points): \(a + b + c + d \le 150\)

Subtask 8 (10 points): \(a + b + c + d \le 200\)

Subtask 9 (10 points): \(a + b + c + d \le 300\)

Subtask 10 (20 points): no additional constraints If, for a test case, your solution does not output a valid polygon that consists of the given sticks, then it scores 0 points for the corresponding subtask. If the solution outputs a valid polygon that is not of the minimal possible area, then it can score partial points according to the following rules. For test case \(j\), let \(r_{j}\) denote the ratio of area of the obtained polygon and the minimal possible polygon area. For subtask \(k\), let’s denote with \(zk\) the largest of the numbers \(rj\), where \(j\) is the test case from subtask \(k\). The percentage of points \(Pk\) that the solution scores for subtask \(k\) depends on the number \(zk\) in the following way: \(P_{k} = 10\) if \(z_{k} \ge 3\), and otherwise it is calculated as: \(Pk\) = ^{25} 8 ^{(3}{z}{)} Therefore, a solution that is not optimal can score between 10% and 60% points for a certain subtask, depending on the ratio of the area of the obtained polygon and the optimal one.}^{+ 10}^{.

The first line of input contains four integers a, b, c, d from the task.

You must output \(n\) lines where \(n = a + b + c + d\). In the \(j\)th line, output integers \(xj\) and \(yj\) — the
coordinates of the \(j\)th polygon vertex. The first polygon vertex must be (0, 0), and the other vertices
can be printed in an arbitrary direction (either positive or negative). It is allowed that the consecutive
polygon sides are parallel, but the polygon cannot touch or intersect itself.
1 sekun\(da / 1024\) M\(iB / 100\) points

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Olympiad