Manhattan

A fost odată un om atât de sărac încât singura sa avere era o turmă de oi aflate în puncte de coordonate naturale nenule strict mai mici decât $5 \ 000$. Din păcate omul nostru a uitat câte oi are și la ce coordonate se află. Singurul lucru pe care și-l mai amintea era suma distanțelor Manhattan de la toate oile sale până la oricare punct de coordonate naturale mai mici egale decât $5 \ 000$. Cum mulțimea de puncte prin care trebuie să-și caute oile e uriașă, vă roagă să îl ajutați să găsească oile pierdute.

Protocol de interacțiune

Programul vostru va trebui să conțină o funcție

void findPoints()

Această funcție trebuie să apeleze de un număr limitat de ori funcția:

long long getDistance(int x, int y)

care va returna suma distantelor Manhattan de la punctul de coordonate $(x, y)$ la toate oile căutate și să apeleze o funcție

void newPoint(int x, int y)

pentru a anunța că a fost găsită o oaie la coordonatele $(x, y)$.

Cele două funcții sunt puse la dispoziția concurenților de către comisie.

Restricții și precizări

• $1 ≤ N ≤ 2 \ 000 \ 000$
• $1 ≤ x, y ≤ 4 \ 999$ pentru oricare din oile căutate
• Pot exista mai multe oi la aceleași coordonate
• $0 ≤ x, y ≤ 5 \ 000$ pentru orice apel al funcției getDistance
• Distanța Manhattan dintre punctele $(x_1, y_1)$ și $(x_2, y_2)$ este $|x_1-x_2|+|y_1-y_2|$
• Pentru $70\%$ din punctaj, numărul de apeluri ale funcției getDistance trebuie să fie cel mult $20 \ 000$.
• Pentru $100\%$ din punctaj, numărul de apeluri ale funcției getDistance trebuie să fie cel mult $9 \ 999$.
• În program trebuie inclus headerul manhattan.h

Exemplu

grader: findPoints()
concurent: getDistance(1, 1)
grader: return 0
concurent: getDistance(1, 2)
grader: return 2
concurent: newPoint(1, 1)
concurent: newPoint(1, 1)

Explicație

Cele două apeluri sunt suficiente pentru a deduce că sunt exact două oi, ambele la coordonatele $(1, 1)$.