Pe o foaie de matematică sunt 5000x5000 de pătrăţele cu latura egală cu 1 cm. Pătrăţelele sunt evident organizate în 5000 de linii (numerotate de sus în jos de la 1 la 5000) şi 5000 de coloane (numerotate de la stânga la dreapta de la 1 la 5000).
Poziţia fiecărui pătrăţel de pe foaie este caracterizată prin numărul liniei şi numărul coloanei pe care se află pătrăţelul. Pe foaie sunt înnegrite
n pătrăţele.
Trebuie să desenăm pe foaia de matematică o mulţime de pătrate care să îndeplinească următoarele condiţii:
− aria intersecţiei între oricare două pătrate din această mulţime este egală cu 0;
− oricare dintre pătratele acestei mulţimi este alcătuit doar din pătrăţele întregi;
− oricare pătrăţel negru aparţine exact unuia dintre pătratele mulţimii;
− pentru oricare dintre pătratele acestei mulţimi, dacă notăm cu
S aria pătratului, atunci suprafaţa ocupată de pătrăţelele negre din interiorul respectivului pătrat aparţine intervalului
[S/k, 4S/k), unde
k este un număr natural nenul dat.
Cerinţă
Scrieţi un program care determine o mulţime de pătrate care să respecte condiţiile de mai sus.
Date de intrare
Fişierul de intrare
patrate4.in conţine pe prima linie două numere naturale nenule separate prin spaţiu
n şi
k, cu semnificaţia din enunţ. Pe fiecare dintre următoarele
n linii se află câte două numere naturale nenule separate prin spaţiu, reprezentând poziţia unui pătrăţel negru.
Date de ieşire
În fişierul de ieşire
patrate4.out se va scrie pe prima linie un număr natural nenul
np, reprezentând numărul de pătrate din mulţime. Pe fiecare dintre următoarele
np linii se vor afla trei numere naturale nenule separate prin câte un spaţiu; primele două valori vor reprezenta linia, respectiv coloana pe care se află pătrăţelul situat în colţul din stânga-sus al pătratului respectiv, iar a treia valoare va reprezenta lungimea laturii respectivului pătrat.
Restricţii
1 ≤ n ≤ 100 000
5 ≤ k ≤ 10
Coordonatele pătrăţelelor negre (linie, coloană) sunt numere naturale din intervalul
[1, 1000].
Exemple
patrate4.in | patrate4.out | Explicaţii |
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
| Există mai multe soluţii posibile. O altă soluţie ar putea fi:
4
1 1 4
5 5 4
7 9 4
10 7 2 |