B. Үнэтэй нөөц

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

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

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

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

Ихэнх компьютерын стратеги тоглоомууд хот барьж, цэрэг авч овгуудыг байлдан дагуулж, нөөц цуглуулахыг шаарддаг. Зарим үед энэ нь сонирхолтой асуудал болж байна.

Чиний даалгавар бол дөрвөлжин хот барих гэж бодъё. Дэлхийн газрын зураг декартын координатуудыг ашигладаг. Хотын талууд координатын тэнхлэгүүдтэй параллель байх ёстой. Газрын зураг нь бүхэл тоон координатуудтай цэг дээр байрласан үнэтэй нөөцтэй уурхайнууд агуулна. Уурхайнуудын хэмжээ харьцангуй жижиг, өөрөөр хэлвэл цэгүүд гэж үзэж болно. Бүх уурхайнууд хотын дотор эсвэл дөрвөлжин хотын хүрээн дээр байхаар хотыг байгуулах ёстой.

Хот байгуулахад хотын хэмжээнээс хамаарч их хэмжээгээр мөнгө шаарддаг, тиймээс чи аль болох бага талбайтай хот барьна. Уурхайнуудын байрлал өгөгдсөн бол хотын боломжит хамгийн бага талбайг ол.

Оролт

Оролтын эхний мөр нь $n$ бүхэл тоог агуулна. Энэ бол газрын зураг дахь уурхайн тоо юм ($2 ≤ n ≤ 1000$). Дараагийн $n$ мөр бүр нь $x_{i}$, $y_{i}$ бүхэл тоон хосуудыг агуулах ба энэ нь харгалзах уурхайн координатууд юм ($ - 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$). Бүх цэгүүд хос хосоороо ялгаатай байна.

Гаралт

Үнэтэй нөөцтэй бүхий бүх уурхайг хамарсан хотын хамгийн бага талбайг хэвлэ.

Орчуулсан: Даариймаа

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

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