Croatian Olympiad in Informatics
April \(25^{th}\) 2021
It is a we\(ll-kn\)own fact that a group of Russian scientists discovered an alien civilization back in 2016.
Their satellite managed to capture \(K\) hi\(gh-re\)solution square images that forever changed the course of
human history. Today, half a decade later, almost every part of the world has its own space program that
investigates aliens. Alas, in Croatia we have decided to tackle some more important problems, which
leaves scientific research on the shoulders of few enthusiasts. Vladimir is one of them.
Unfortunately, Vladimir doesn’t have enough resources for a spacecraft or an expensive telescope, but he
can afford a h\(ot-ai\)r balloon and a mobile phone. Instead of an alien civilization, he decided to search
for signs of intelligent life on his home planet. Looking down from the balloon, Vladimir notices exactly
\(N\) people. He decided to capture exactly \(K\) square images of average resolution such that each person
is seen on exactly one image. Also, he doesn’t want any detail to be visible on more than one image.
Furthermore, he finds it important that the largest area visible on some picture is as small as possible.
Vladimir is not a great programmer, so he sent you a formal specification and awaits your help.
Formal specification
There are \(N\) integer points in the coordinate system. You need to find exactly \(K\) disjunct squares that
cover all \(N\) points. The squares must have sides parallel with the coordinate axes and their vertices should
lie on integer coordinates. The area of the largest square needs to be as small as possible.
We say that a square covers a point if the point is fully inside it or lies on its vertices or sides. Two squares
are disjunct if their sides doesn’t intersect or touch, and neither of the squares is fully contained in the
other square.

Subtask 1 (5 points): \(1 \le N \le 100\,000\), \(K = 1\)

Subtask 2 (21 points): \(1 \le N \le 100\,000\), \(K = 2\)

Subtask 3 (12 points): \(1 \le N \le 12\), \(K = 3\)

Subtask 4 (30 points): \(1 \le N \le 1\,000\), \(K = 3\)

Subtask 5 (32 points): \(1 \le N \le 100\,000\), \(K = 3\ 4\) od 7 Croatian Olympiad in Informatics April \(25^{th}\) 2021

The first line contains integers \(N\) and \(K\) from the task description.
The \(i-th\) of the next \(N\) lines contains integers \(x@@RISE_MATH_BLOCK_0@@i\) (0 ≤|\(x@@RISE_MATH_BLOCK_1@@i\)| ≤\(10^{9}\)) that represent the coordinates
of the \(i-th\) point (person). All \(N\) points will be different.

The \(i-th\) of the \(K\) lines should contain three integers \(x_{i}\), \(y_{i}\) (0 ≤|\(x_{i}\)|, |\(y_{i}\)| ≤\(3 \cdot 10^{9}\)) and \(l_{i}\) (\(1 \le l_{i} \le 2 \cdot 10^{9}\)),
that uniquely define the location of the \(i-th\) square, such that the point (\(x@@RISE_MATH_BLOCK_0@@i\) denotes its side length.
If there are multiple correct solutions, output any of them.

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

출처 COCI 2020/2021 Olympiad