patrate4

Patrate 4

== include(page="template/taskheader" task_id="patrate4") ==

Poveste si cerinta...

Pe o foaie de matematica sunt $5000 x 5000$ de patratele cu latura egala cu $1 cm$. Patratelele sunt evident organizate in $5000$ de linii (numerotate de sus in jos de la $1$ la $5000$) si $5000$ de coloane (numerotate de la stanga la dreapta de la $1$ la $5000$).
 
Pozitia fiecarui patratel de pe foaie este caracterizata prin numarul liniei si numarul coloanei pe care se afla patratelul. Pe foaie sunt innegrite $N$ patratele.
 
Trebuie sa desenam pe foaia de matematica o multime de patrate care sa indeplineasca urmatoarele conditii:
 
* 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.
 
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") ==

1911