Problem #141

3dist

Time limit: 1.85s
Memory limit: 256MB
Input: stdin
Output: stdout

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

Date de intrare

De pe prima linie 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.

Date de ieșire

Pe prima linie se va afișa un singur număr S reprezentând răspunsul întrebării lui Țeba.

Restricții

  • 1 ≤ N ≤ 250 000
  • \(0 ≤ X_i, Y_i ≤ 10^9\) pentru oricare 1 ≤ i ≤ N
  • Nu vor exista două locuințe aflate la aceleași coordonate.

Subtask 1 (7 puncte)

  • N ≤ 100

Subtask 2 (14 puncte)

  • N ≤ 2 000

Subtask 3 (28 puncte)

  • \(X_i, Y_i ≤ 2 000\) pentru oricare 1 ≤ i ≤ N

Subtask 4 (51 puncte)

  • Fără restricții suplimentare

Exemple

stdin

5
1 1
3 1
2 2
2 6
4 4

stdout

1 

Explicații

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.

General info

Uploader: liviu

Author: Bogdan-Ioan Popa, Andrei-Costin Constantinescu

Source: ONI 2022 Baraj 1 Seniori: Problema 1

Submissions