* aria intersectiei intre oricare doua patrate din aceasta multime este egala cu $0$;
* oricare dintre patratele acestei multimi este alcatuit doar din patratele intregi;
* oricare patratel negru apartine exact unuia dintre patratele multimii;
* pentru oricare dintre patratele acestei multimi, daca notam cu $S$ aria patratului, atunci suprafata ocupata de patratelele negre din interiorul respectivului patrat apartine intervalului $[S / k, 4S / k)$, unde $k$ este un numar natural nenul dat.
* pentru oricare dintre patratele acestei multimi, daca notam cu $S$ aria patratului, atunci suprafata ocupata de patratelele negre din interiorul respectivului patrat apartine intervalului $[S / K, 4S / K)$, unde $K$ este un numar natural nenul dat.
h2. Cerinta
Scrieti un program care determine o multime de patrate care sa respecte conditiile de mai sus.
h2. Date de intrare
...
Fisierul de intrare $patrate4.in$ contine pe prima linie doua numere naturale nenule separate prin spatiu $N$ si $K$, cu semnificatia din enunt. Pe fiecare dintre urmatoarele $N$ linii se afla cate doua numere naturale nenule separate prin spatiu, reprezentand pozitia unui patratel negru.
h2. Date de iesire
...
In fisierul de iesire $patrate4.out$ se va scrie pe prima linie un numar natural nenul $np$, reprezentand numarul de patrate din multime. Pe fiecare dintre urmatoarele $np$ linii se vor afla trei numere naturale nenule separate prin cate un spatiu; primele doua valori vor reprezenta linia, respectiv coloana pe care se afla patratelul situat in coltul din stanga-sus al patratului respectiv, iar a treia valoare va reprezenta lungimea laturii respectivului patrat.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $5 ≤ K ≤ 10$
* Coordonatele patratelelor negre (linie, coloana) sunt numere naturale din intervalul $[1, 1000]$.
h2. Exemplu
table(example). |_. patrate4.in |_. patrate4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 19 5
1 1
1 2
2 1
2 2
3 1
3 3
4 3
5 5
5 6
5 7
6 6
6 7
10 7
10 8
7 9
8 10
8 9
9 9
10 9
| 2
1 1 4
5 5 6
|
h3. Explicatie
...
Exista mai multe solutii posibile. O alta solutie ar putea fi:
$4
1 1 4
5 5 4
7 9 4
10 7 2$
== include(page="template/taskfooter" task_id="patrate4") ==
