Feladat

Adott egy város a négyzetrácson. Az utcák a tengelypárhuzamos, rácspontokon keresztül húzott egyenesek, közülük a főút az x-tengely. A polgármester tűzijátékot szeretne rendezni a főút valamelyik rácspontjában, azonban azt csak a rácsponton keresztül haladó utcákról lehet látni. Tehát ha a (p,0) pontban rendezi, akkor azt a főútról, valamint az x=p egyenesről látni. A helyszínt úgy akarja kiválasztani, hogy a (fontosabb) városlakóknak minél kevesebbet kelljen sétálni ahhoz, hogy megnézhessék a tűzijátékot. A sétatáv Manhattan-távolságban értendő, azaz csak utcákon sétálhatnak, és szomszédos utcák közt egy egységnyi utat kell megtenni.

Még egy megkötés van, mégpedig hogy a balesetek elkerülése végett a nézőknek legalább S egységnyire kell állni a tűzijátéktól. A kérdés pedig az, hogy hol legyen a tűzijáték, hogy összességében a lehető legkevesebbet kelljen a lakóknak sétálni ahhoz, hogy a két út valamelyikén, biztonságos távolságból nézhessék azt. Természetesen tudjuk, hogy ők hol laknak.

input

A bemenet első sora két egész szám, a lakók száma (N<=100 000) és S<=1 000 000. A következő N sor mindegyike két egész számot, az i-edik lakó lakhelyének y- és x-koordinátáit (igen, ilyen sorrendben) tartalmazza. (Mindenki utcasarkon lakik, és egy kereszteződésnél akár többen is.)

output

Kiírni egyetlen egész számot kell, a minimálisan legyalogolandó össztávolságot, egységekben mérve.

BalticOI 2012

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.