Programozó versenyek

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

2022. december 4. 10:00 – 2022. december 4. 15:15

Hálózat kábelezés

A Debreceni Egyetem Informatikai Karán egy új számítógépes labor került átadásra. A PC-k már el vannak helyezve, azonban a hálózat még nincs bekötve. Mivel a rendszergazdáink igen elfoglaltak, így ránk vár a feladat, hogy a lehető legkevesebb hálózati kábel felhasználásával bekössük az internetet az összes gépre.
A kábelezés módosított busztopológia alapján történik, melynek lényege a következő:
  • Minden számítógép rendelkezik egy x és y koordinátával, mely a teremben elfoglalt helyét jelenti. A (0,0) koordináta bárhol lehet a teremben, így előfordulhat, hogy néhány számítógép negatív koordinátákkal rendelkezik.
  • Készíteni kell egy balról jobbra haladó, X-tengellyel párhuzamos fővezetéket melynek kezdete a balszélső számítógép x koordinátája, a vége pedig a jobbszélső PC x koordinátája.
  • Erről a fővezetékről ágaznak le merőlegesen az egyes PC-kig haladó kábelszakaszok.
  • A fővezeték áthaladhat a számítógépeken is, ilyenkor az adott PC-t bekötöttnek tekintjük.
  • A fővezetékről leágazó vezetékek nem haladhatnak át számítógépeken, azaz ha két PC-nek ugyanaz az x koordinátája, akkor a fővezetéknek vagy a kettő között kell lennie, vagy az egyiken át kell haladnia.

Input

  • A bemenet első sora egy N pozitív egész, mely a bekötendő számítógépek számát adja meg;
  • A következő N darab sor mindegyike egy szóközzel elválasztott x és y egész számot tartalmaz, mely egy számítógép teremben elfoglalt koordinátáit adja meg.

Output

A kimenet egyetlen pozitív egész szám, mely megadja, hogy összes számítógép, fentebb részletezett módon történő bekötése legkevesebb hány "hossznyi" kábellel oldható meg.

Megkötések

  • 0 < N < 100000;
  • A helyes megoldás legfeljebb 263;
  • -230 ≤ x,y ≤ 230

Példa

Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.