D. Сережа ба шулуунууд

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

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

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

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

Сережа хавтгай дээр $n$ цэг зурав. Одоо Сережа хавтгай дээр тэгш өнцөг үүсгэн огтлолцсон хоёр шулуун татахыг хүсэж байгаа ба нэг шулуун нь $Ox$ тэнхлэгтэй $45$ градус үүсгэх юм. Мөн цэгүүдээс уг $2$ шулуун хүрэх хамгийн хол зайг нь бага байлгахыг хүсэж байв.

Энэ бодлогонд бид ($x_1,y_1$) ба ($x_2,y_2$) хоёр цэгийн хоорондох зайг $|x1-x2|+|y1-y2|$-тай тэнцүү гэж тооцно. Цэгээс шулуун хүртлэх зай гэдэгт тухайн цэгээс шулуун дээрх цэгүүдийн хамгийн ойрхон руу хүрэх зай гэж ойлгоно.

Сережа шулуунуудыг хүссэнээрээ байрлуулж чадсан бол ийнхүү оптимал байрласан шулуунууд хүрэх хамгийн их зайг ол.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^5$). Дараагийн $n$ мөрөнд мөр бүрд цэгүүдийн координатыг илэрхийлэх $x_i$, $y_i$ ($|xi|,|yi| ≤ 10^9$) тоонууд байна.

Гаралт

Хариу болох бодит тоо. Үндсэн хариутай $10^{-6}$-аас багаар зөрж болно.

Орчуулсан: gmunkhbaatarmn

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

Оролт
4
0 0
2 0
0 2
2 2
Гаралт
0.000000000000000
Оролт
4
1 0
0 1
2 1
1 2
Гаралт
1.000000000000000
Сэтгэгдлүүдийг ачааллаж байна...