== include(page="template/taskheader" task_id="beyond_the_wall") ==
Se dau n puncte si q drepte. Se cere numarul de puncte care se afla sub drepta.
h2. Date de intrare
Copiii pădurii se feresc de "ceilalţi" aşa că îsî propun să construiască un mare zid pentru a îi ţine la distanţă de restul tărâmului. Se cunoaşte faptul că există puncte în plan care nu au stabilitate aşa că ei doresc să construiască un zid care e cât mai ferit de aceste puncte. Astfel ei şi-au pregătit deja anumite întrebări sub forma "Fiind dată o dreaptă să se răspundă la întrebarea: Câte puncte instabile se află strict sub dreptă?". Deoarece doar tu cunoşti poziţia punctelor şi întrebările lor, ei se pot baza doar pe tine să le răspunzi.
Fişierul de intrare $beyond_the_wall.in$ ...
h2. Date de intrare
N, Q
N puncte
Q drepte date prin M, B
Y = MX + B
Fişierul de intrare $beyond_the_wall.in$ conţine pe prima linie numerele $N$ şi $Q$ care reprezintă numărul punctelor instabile, respectiv numărul întrebărilor.
Pe următoarele $N$ linii se vor afla coordonatele punctelor.
Pe următoarele $Q$ linii se vor afla câte două numere $M$, $B$ care descriu ecuaţia dreptei $Y = MX + B$
h2. Date de ieşire
În fişierul de ieşire $beyond_the_wall.out$ ...
Q numere
În fişierul de ieşire $beyond_the_wall.out$ se vor găsi $Q$ numere, câte unul pe linie, numărul de pe linia $i$ reprezentând răspunsul la întrebarea $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $Toate numerele din input sunt întregi$
* $1 ≤ N ≤ 40000$
* $-10^5^ ≤ M, B ≤ 10^5^$
* $1 ≤ Q ≤ 2 * 10^5^$
* $1 ≤ N * Q ≤ 4 * 10^9^$
* $-10^5^ ≤ X{~i~}, Y{~i~} ≤ 10^5^$
* $Pentru 5 puncte: 1 ≤ N ≤ 100 şi 1 ≤ Q ≤ 100$
* $Pentru alte 60 puncte: 1 ≤ N ≤ 5000 şi 1 ≤ N * Q ≤ 4 * 10^9^$
* $Pentru restul de 35 puncte: Restricţiile iniţiale$
* Un punct $(X{~i~}, Y{~i~})$ se află sub dreapta de ecuaţie $Y = MX + B$ dacă $MX{~i~} - Y{~i~} + B > 0$
h2. Exemplu
table(example). |_. beyond_the_wall.in |_. beyond_the_wall.out |
| 8 4
-8 4
-2 6
8 4
2 8
-8 -4
-2 -6
6 -2
0 -2
1 0
3 -6
-2 -5
-5 7
| 4
2
| 4 2
1 3
4 2
6 4
7 1
-1 6
3 -4
| 1
3
5
|
h3. Explicaţie
...
!problema/beyond_the_wall?beyond_ex.png 500x500!
Observăm că pentru prima întrebare punctul B (4, 2) nu este luat în calcul la răspuns deoarece se află pe dreaptă.
== include(page="template/taskfooter" task_id="beyond_the_wall") ==
