== include(page="template/taskheader" task_id="3dist") ==

Poveste şi cerinţă...

Noul cartier din Buguré face mari furori în toată ţara. Acesta este alcătuit din $N$ locuinţe care pot fi cumpărate, a $i$-a locuinţă aflându-se la coordonatele $(X{~i~}, Y{~i~})$. Notăm cu $dist(i, j) = |X{~i~} − X{~j~}| + |Y{~i~} − Y{~j~}|$ şi $d(i) = min{~{j≠i}~}(dist(i, j))$
 
Fiind prieteni din copilărie şi nedespărţiţi, $*Àles*$, $*RANDy*$ şi $*Ţeba*$ doresc să fie şi ei în rând cu lumea bună şi decid să achiziţioneze şi ei locuinţe, câte una pentru fiecare. Cei trei ţin foarte mult la relaţia lor şi fiecare doreşte să aibă ceva de spus în alegerea locuinţelor, aşa că ei convin următoarele:
 
* $*À* < *R* < *Ţ*$
* $dist($ $*À*$ $,$ $*R*$ $) = dist($ $*R*$ $,$ $*Ţ*$ $) = dist($ $*À*$ $,$ $*Ţ*$ $)$
* $d($ $*À*$ $) = d($ $*R*$ $) = d($ $*Ţ*$ $) = dist($ $*À*$ $,$ $*R*$ $)$
 
unde notăm cu iniţiala numelui fiecăruia numărul de ordine al casei pe care o cumpără fiecare.
 
La o analiză mai detaliată, $*Ţeba*$, creierul echipei, observă că au foarte multe alegeri posibile şi îşi pune întrebarea: "în câte moduri ne putem alege locuinţele astfel încât cerinţele de mai sus să fie respectate?".

h2. Date de intrare

Fişierul de intrare $3dist.in$ ...

De pe prima linie a fişierul de intrare $3dist.in$ se va citi numărul natural $N$. Pe următoarele $N$ linii se află câte două numere $X{~i~}, Y{~i~}$, reprezentând coordonatele locuinţelor.

h2. Date de ieşire

În fişierul de ieşire $3dist.out$ ...

Pe prima linie a fişierul de ieşire $3dist.out$ se va afişa un singur număr $S$ reprezentând răspunsul întrebării lui $*Ţeba*$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 250 000$
* $0 ≤ X_i, Y_i ≤ 1 000 000 000 (10^9^)$
* Nu vor exista două locuinţe aflate la aceleaşi coordonate.
 
h2. Subtaskuri
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $7$ | $N ≤ 100$ |
| $2$ | $14$ | $N ≤ 2 000$ |
| $3$ | $28$ | $X{~i~}, Y{~i~} ≤ 2 000$ pentru orice $1 ≤ i ≤ N$ |
| $4$ | $51$ | Fără restricţii suplimentare |

h2. Exemplu
table(example). |_. 3dist.in |_. 3dist.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
  1 1
  3 1
  2 2
  2 6
  4 4
| 1

|
h3. Explicaţie

...

Singurul triplet care respectă cerinţele este: $(1, 2, 3)$. Tripletul $(3, 4, 5)$ respectă $dist(3, 4) = dist(4, 5) = dist(3, 5)$ însă $d(3) = 2, d(5) = 4$ şi $d(4) = 4$.

== include(page="template/taskfooter" task_id="3dist") ==