Fişierul intrare/ieşire:norocoase.in, norocoase.outSursăSapientia ECN 2016
AutorPaul DiacAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Norocoase

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?

Date de intrare

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.

Date de ieşire

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

Restricţii

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

Exemplu

norocoase.innorocoase.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 iniţiale (5, 11), (3, 9), (2, 7), (2, 4), (3, 2) pot fi norocoase:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?