Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | norocoase.in, norocoase.out | Sursă | Sapientia ECN 2016 |
| Autor | Paul Diac | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Norocoase
Fie P un poligon convex cu N varfuri: (x[i], y[i]) unde ambele coordonate ale fiecarui punct sunt numere naturale. Poligonul se poate roti cu orice panta.
Dupa rotatie se considera cel mai de jos varf: cel cu y[i] cel mai mic, fie aceasta valoare ymin. Toate punctele care au y[i] dupa rotatie in intervalul [ymin, ymin + W] sunt considerate norocase, unde W este un numar natural dat.
Care este numarul maxim de varfuri norocoase care se pot obtine rotind poligonul corespunzator?
Date de intrare
Fişierul de intrare norocoase.in contine pe prima linie numarul de teste T. Urmeaza pe rand descrierea pentru fiecare test:
Prima linie contine numerele N si W, numarul de varfuri si latimea W.
Urmatoarele N linii contin doua numere naturale x[i] si y[i], coordonatele initiale ale punctelor in ordine. Ordinea poate fi trigonometrica sau ordinea acelor de ceasornic.
Date de ieşire
În fişierul de ieşire norocoase.out afisati raspunsul pentru fiecare test in ordine: numarul maxim de puncte care pot fi norocoase dupa rotatie.
Restricţii
- ... ≤ ... ≤ ...
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 0 ≤ x[i], y[i], W ≤ 109
- Rotatia poate fi facuta cu un numar fractionar de grade: se poate roti cu orice precizie.
Exemplu
| norocoase.in | norocoase.out |
|---|---|
| 1 8 3 9 1 11 5 9 10 5 11 3 9 2 7 2 4 3 2 | 5 |
Explicaţie
Punctele cu coordonatele initiale (5, 11), (3, 9), (2, 7), (2, 4), (3, 2) pot fi norocoase:
