|
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
|
|