Počet bodov:
Popis:  12b
Program:  8b

V Manhattane kedysi stáli dvojičky. Kolumbus objavil Ameriku, one thing led to another a dvojičky dnes už v Manhattane nestoja. Finančníci, ktorí v dvojičkách pracovali, sa rozpŕchli po celom Manhattane.

Nieje nad vzťah založený na peniazoch, a tak ešte dodnes neustále medzi sebou kadečo vybavujú – odcestujú na nové pracovisko ich známeho, prehrabnú sa v kufríku plnom papierov, podpíšu niečo čo nikto nikdy nečítal, a vrátia sa naspäť do práce. A keď sa vydarí, po ceste sa ešte zastavia u kamaráta, vypijú kávu, zaspomínajú na strašidelné časy kedy si aj úplne obyčajní ľudia vedeli dovoliť nový, priestorný byt, a pokračujú v pracovnej ceste. Svojim nadriadeným toto drobné zdržanie vysvetlia ako zápchu v poludňajšej New Yorkskej1 premávke, a veselo si celú cestu pripíšu do firemného času.

Ale takéto výhovorky nefungujú vždy – ak by kvôli priateľskej návšteve finančník robil dajaké obkľuky, určite by mu na to nadriadení prišli2. Takúto zastávku sa teda odhodlajú urobiť len vtedy, keď nezvýšia prejdenú vzdialenosť k ich ozajstnej destinácií.

FKS3 sa rozhodol vyčísliť, koľko takýchto návštev môže denne prebiehať. Vrámci znižovania nákladov však programátorské práce outsourceli na Slovenské stredné školy…

Úloha

Všetky budovy Manhattanu perfektne zapadajú do štvorčekovej mriežky.

Zadané sú súradnice budov v Manhattane, v ktorých pracujú finančníci.

Keďže sú v Manhattane, vzdialenosť medzi budovami je samozrejme Manhattanovská – budova so súradnicami \((x_1 , y_1)\) je od budovy so súradnicami \((x_2 , y_2)\) vzdialená \(|x_1 - x_2| + |y_1 - y_2|\).

Finančník cestujúc z budovy A do budovy B sa môže po ceste zastaviť pri budove C práve vtedy, keď vzďialenosť budov A a B je rovná vzdialenosti budov A a C plus vzdialenosti budov C a B.

Vyhodnotťe, koľko rôznych pocestných návštev sa môže v Manhattane odohrať. Dve návštevy považujeme za rôzne ak sa líšia v štartovnej, cieľovej, alebo navštívenej budove.

Formát vstupu

V prvom riadku je číslo \(n\) – počet finančníkov v Manhattane. Každý z nasledujúch \(n\) riadkov obsahuje dve celé čísla \(x_i\ y_i\) – súradnice budovy, v ktorej pracuje \(i\)-ty finančník. Súradnice budov sú navzájom rôzne.

Pre testovacie sady pritom platí nasledovné:

Sada 1 2 3 4
\(1\leq n\leq\) \(200\) \(2\,000\) \(200\,000\) \(200\,000\)
\(0\leq x_i, y_i\leq\) \(1\,000\) \(1\,000\) \(1\,000\) \(1\,000\,000\)

Formát výstupu

Vypíšte jediné číslo – počet rôznych návštev, ktoré medzi sebou dokážu finančníci urobiť.

Príklady

Input:

3
2 2
3 2
4 2

Output:

2

Návštevu v druhej budove si môžu dovoliť finančníci cestujúci z prvej do tretej budovy, a naopak.

Input:

4
2 2
3 2
4 2
1 1

Output:

8

Teraz môžu navyše prvú budovu navštíviť finančníci zo štvrtej budovy na ceste do druhej alebo tretej (a naopak), a druhú budovu na ceste do tretej (a naopak).


  1. Kedy ste naposledy videli v slove ‘rksk’?↩︎

  2. pomocou GPS trackingu firemných vozidiel↩︎

  3. Finačný Korupčný Sektor↩︎

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.