#P8389. [COI2021] Izvanzemaljci

[COI2021] Izvanzemaljci

题目描述

译自 COI 2021 T3「Izvanzemaljci

在二维平面上有 NN 个整点 (xi,yi)(x_i,y_i),请找出 KK 个不相交的正方形,使得所有整点在正方形内或在正方形上,如有多解,求出在所有构造方案中面积最大的正方形面积最小的那一种,如果还有多解,输出任意一组即可。

两个正方形如果没有边相交或相碰,并且没有一个正方形完全被另一个正方形包含的情况,则这两个正方形不相交。

输入格式

第一行为两个整数 NNKK

接下来 NN 行,一行两个整数 xix_iyiy_i

输出格式

KK 行,每行三个整数 aia_ibib_ilil_i,表示有一个左下角为 (ai,bi)(a_i,b_i),边长为 lil_i 的正方形。

您需要保证 0ai,bi3×1090\le |a_i|,|b_i|\le 3\times 10^91li2×1091\le l_i\le 2\times 10^9

3 1
1 1
1 3
2 2
0 1 2
5 2
1 3
3 1
5 5
5 10
7 7
1 1 4
5 7 3
5 3
1 3
3 1
5 5
5 10
7 7

1 1 2
5 5 2
5 10 1

提示

【样例解释】

样例 #2 解释:

样例 #3 解释:

【数据范围】

对于全部数据,有 1N1051\le N\le 10^51K31\le K\le 30xi,yi1090\le |x_i|,|y_i|\le 10^9

Subtask 限制 分数
11 K=1K=1 55
22 K=2K=2 2121
33 N12N\le 12K=3K=3 1212
44 N103N\le 10^3K=3K=3 3030
55 K=3K=3 3232