P16190 [COI 2018] Pick Pick

1 s, 1024 MB.

Mirko recently read about *Pick’s theorem*, which says: On a coordinate plane, if we draw a polygon whose vertices all have integer coordinates, let its area be $A$, let the number of integer-coordinate points strictly inside the polygon be $i$, and let the number of integer-coordinate points on the boundary of the polygon (including vertices) be $b$. Then it always holds that: $$A=i+\frac{b}{2}-1$$ To verify this theorem, Mirko used his smart whiteboard and made a polygon using magnetic sticks. Due to gravity, during the night the sticks may have slid down to the bottom of the whiteboard. Now, Mirko wants to build a polygon with the smallest possible area while using all the sticks he can find. Mirko may move the sticks on the whiteboard, but he must not rotate them. He has the following sticks: - $a$ horizontal sticks of length 1, - $b$ vertical sticks of length 1, - $c$ diagonal sticks of length $\sqrt{2}$, forming a $45\degree$ angle with the positive direction of the $x$-axis, - $d$ diagonal sticks of length $\sqrt{2}$, forming a $135\degree$ angle with the positive direction of the $x$-axis.  Figure 2: The polygon above: $A = 8$, $i = 4$, $b = 10$.  Figure 3: The sticks Mirko has. Determine a polygon with the minimum possible area that can be built such that all sticks are used. You may assume the input guarantees that at least one polygon can be constructed. If you construct a valid polygon using all given sticks (not necessarily with minimum area), you can also get partial points. For more details, see the “Scoring” section.

The first line contains four integers, which are $a, b, c, d$ as described in the statement.

Output $n$ lines, where $n = a + b + c + d$. On the $j$-th line, output integers $x_j$ and $y_j$—the coordinates of the $j$-th vertex of the polygon. The first vertex must be $(0, 0)$. The remaining vertices may be printed in any direction (clockwise or counterclockwise). Consecutive polygon edges are allowed to be parallel, but the polygon must not self-intersect or self-touch.

### Constraints In all subtasks, $0 \le a, b, c, d \le 100$ and $a + b + c + d \ge 3$. ### Subtasks ::cute-table{three} | ID | Points | Constraints | |:--:|:--:|:--:| | $1$ | $5$ | $c = d = 0$ | | $2$ | $5$ | $a = b = 0$ | | $3$ | $10$ | $a + b + c + d \le 6$ | | $4$ | $10$ | $a + b + c + d \le 20$ | | $5$ | $10$ | $a + b + c + d \le 40$ | | $6$ | $10$ | $a + b + c + d \le 80$ | | $7$ | $10$ | $a + b + c + d \le 150$ | | $8$ | $10$ | $a + b + c + d \le 200$ | | $9$ | $10$ | $a + b + c + d \le 300$ | | $10$ | $20$ | No additional constraints | ### Scoring If, for some test case, your solution does not output a valid polygon, then that subtask scores $0$ points. If the output polygon is valid but not of minimum area, it can still receive partial points: For test case $j$, let $r_j$ be the ratio of the output polygon’s area to the minimum possible area. For subtask $k$, let $z_k$ be the maximum of all $r_j$ in subtask $k$. The percentage score $P_k$ is computed as follows: if $z_k \ge 3$, then $P_k = 10$. Otherwise: $$P_k = \frac{25}{8}(3 - z_k)^4 + 10$$ Therefore, a non-optimal solution can obtain between $10\%$ and $60\%$ of the score in a subtask, depending on the polygon area ratio. Translation source: GPT 4.1 mini. Translated by ChatGPT 5