== include(page="template/taskheader" task_id="norocoase") ==
Poveste şi cerinţă...
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.
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 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$ ...
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$ ...
Î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
* 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
table(example). |_. norocoase.in |_. norocoase.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
8 3
9 1
11 5
9 10
5 11
3 9
2 7
2 4
3 2
| 5
|
h3. Explicaţie
...
Punctele cu coordonatele iniţiale (5, 11), (3, 9), (2, 7), (2, 4), (3, 2) pot fi norocoase:
!problema/norocoase?desen.png!
== include(page="template/taskfooter" task_id="norocoase") ==
