Fişierul intrare/ieşire:pante.in, pante.outSursăLot Cluj 2009, Baraj 5
AutorMircea Bogdan PasoiAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pante

După o înfrângere cruntă, Zăhărel a renunţat să mai joace StarCraft şi a decis să mai rezolve o problemă de informatică. Astfel, el are N puncte în plan, de coordonate numere naturale. El primeşte patru numere naturale A, B, C şi D, şi ştie că panta dreptei care trece prin două puncte i şi j se defineşte astfel:  m(i, j) = \dfrac{y_j - y_i}{x_j - x_i} . El doreşte să afle numărul de perechi de puncte i j (1 ≤ i < j ≤ N) cu proprietatea că  \dfrac{A}{B} \le m(i, j) \le \dfrac{C}{D} .

Cerinţă

Fiind date N puncte în plan, să se afle câte perechi de puncte i j (i < j) au proprietatea  \dfrac{A}{B} \le m(i, j) \le \dfrac{C}{D} .

Date de intrare

Fişierul de intrare pante.in conţine pe prima linie numărul natural N. Pe cea de a doua linie se află numerele naturale A B C D separate prin câte un singur spaţiu. Pe fiecare dintre următoarele N linii se găsesc coordonatele x y ale fiecărui punct.

Date de ieşire

Fişierul de ieşire pante.out va conţine o singură linie pe care este scris numărul de perechi cu proprietatea cerută.

Restricţii şi precizări

  • 1 ≤ N ≤ 200 000
  • 0 ≤ xi, yi ≤ 2 000 000 000
  • 0 < A, B, C, D ≤ 2 000 000 000
  • Pentru 10% dintre teste 1 ≤ N ≤ 700.
  • Oricare două puncte au abscisa diferită.

Exemplu

pante.inpante.out
3
1 2 1 1
0 0
1 1
2 0
1

Explicaţie

Perechea de puncte (1, 2) are proprietatea cerută. Perechea (2, 3) are panta -1, iar perechea (1, 3) are panta 0.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content