norocoase

Norocoase

== include(page="template/taskheader" task_id="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.

Fie **P** un poligon convex cu **N** varfuri: ( **x[i]**, **y[i]** ) unde ambele coordonate ale fiecărui punct sunt numere naturale. Poligonul se poate roti cu orice unghi.

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.

După rotaţie se consideră cel mai de jos vârf: cel cu **y[i]** minim, fie aceasta valoare **ymin**. Toate punctele care au **y[i]** după rotaţie în intervalul **[ymin, ymin + W]** sunt norocoase, unde **W** este un număr natural dat.

Care este numarul maxim de varfuri norocoase care se pot obtine rotind poligonul corespunzator?

Care este numărul maxim de vârfuri norocoase care se pot obţine rotind poligonul corespunzator?

h2. 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.

Fişierul de intrare $norocoase.in$ conţine pe prima linie numărul de teste **T**. Urmează pe rând descrierea pentru fiecare test:
Prima linie numerele **N** şi **W** reprezentând numărul de vârfuri şi laţimea **W**.
Următoarele **N** linii conţin două numere naturale **x[i]** şi **y[i]**, coordonatele iniţiale ale punctelor în ordine. Ordinea poate fi trigonometrică sau ordinea acelor de ceasornic.

h2. 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.

În fişierul de ieşire $norocoase.out$ afişaţi răspunsul pentru fiecare test în ordine: numărul maxim de puncte care pot fi norocoase după rotaţie.

h2. Restricţii

* $... ≤ ... ≤ ...$
* 1 ≤ T ≤ 10
* 1 ≤ N ≤ 10^5^
* 0 ≤ x[i], y[i], W ≤ 10^9^
* Rotatia poate fi facuta cu un numar fractionar de grade: se poate roti cu orice precizie.

* 1 ≤ **T** ≤ 10
* 3 ≤ **N** ≤ 10^5^
* 0 ≤ **x[i], y[i], W** ≤ 10^9^
* Rotaţia poate fi făcută cu un numar fracţionar de grade: se poate roti cu orice precizie.

h2. Exemplu

h3. Explicaţie

Punctele cu coordonatele initiale (5, 11), (3, 9), (2, 7), (2, 4), (3, 2) pot fi norocoase:

Punctele cu coordonatele iniţiale (5, 11), (3, 9), (2, 7), (2, 4), (3, 2) pot fi norocoase:

{! problema/norocoase?desen.png 7% !}

!problema/norocoase?desen.png!

== include(page="template/taskfooter" task_id="norocoase") ==