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

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?".

Poveste şi cerinţă...

h2. Date de intrare

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.

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

h2. Date de ieşire

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*$.

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

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 |

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

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

|
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") ==