E. Чөтгөр

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Декартын 2 хэмжээст хавтгай дээр $n$ хот байв. 2 хотын хоорондын зай Манхаттены зайгаар (доор гарах тайлбар дээр тодорхой байгаа) олдоно. Хамилтоны цикл гэдгийг бүх $n$ хотын дамжлага(нэг хотыг зөвхөн 1 л удаа дайрна) гэж ойлгоё. Хамилтоны циклийн хэмжээ гэж энэ дамжлага дахь хөрш 2 хотын хоорондын зайнуудын нийлбэр дээр эхлэл төгсгөлийн хотуудын хоорондын зайг нэмсэнийг хэлнэ. Тэгвэл эдгээр хотууд дахь хамгийн их боломжит Хамилтоны циклийн хэмжээг ол.

Оролт

Эхний мөрөнд хотуудын тоо $n$ ($3\le n\le 10^5$). Дараагийн $n$ мөрөнд хотуудын координат болох $x_i$ ба $y_i$ ($0\le x_i , y_i\le 10^9$) тоонууд байна. Бүх цэгүүд ялгаатай байна.

Гаралт

Хамгийн их Хамилтоны циклийн хэмжээ болох нэг тоог хэвлэнэ.

C++ хэл дээр 64-bit бүхэл тоо хэвлэхдээ %lld - ийг бүү ашиглаарай. Энд cin , cout юмуу %I64d - ийг ашиглах нь илүү тохиромжтой.

Орчуулсан: Garid

Жишээ тэстүүд

Оролт
4
1 1
1 2
2 1
2 2
Гаралт
6

Тэмдэглэл

Жишээн дээр хамгийн их Хамилтоны циклийн хэмжээ нь($1,1$) ($1,2$) ($2,1$) ($2,2$) циклийн хэмжээ буюу $6$ байна.

($x_i,y_i$) ба ($x_j,y_j$) гэсэн 2 хотын хоорон дахь Манхаттены зай гэж $\mid x_i - x_j\mid + \mid y_i - y_j\mid$ - ыг хэлнэ.

Сэтгэгдлүүдийг ачааллаж байна...