| Fişierul intrare/ieşire: | 3dist.in, 3dist.out | Sursă | ONI 2022 Baraj Seniori Ziua 1 |
| Autor | Andrei-Costin Constantinescu, Bogdan-Ioan Popa | Adăugată de |  Voicu Mihai Valeriu •cadmium_ |
| Timp execuţie pe test | 2.75 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 (Xi, Yi). Notăm cu dist(i, j) = |Xi − Xj| + |Yi − Yj| ş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 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 Xi, Yi, reprezentând coordonatele locuinţelor.
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.
Restricţii
- 1 ≤ N ≤ 250 000
- 0 ≤ X_i, Y_i ≤ 1 000 000 000 (109)
- Nu vor exista două locuinţe aflate la aceleaşi coordonate.
Subtaskuri
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 7 | N ≤ 100 |
| 2 | 14 | N ≤ 2 000 |
| 3 | 28 | Xi, Yi ≤ 2 000 pentru orice 1 ≤ i ≤ N |
| 4 | 51 | Fără restricţii suplimentare |
Exemplu
| 3dist.in | 3dist.out |
|---|---|
| 5 1 1 3 1 2 2 2 6 4 4 | 1 |
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.
