Tarlanın kiçildilməsi (Bürünc)#10570
Fermer Consun bütün inəyi onun ikiölçülü tarlasında müxtəlif nöqtələrdə yerləşir. FC bütün inəklərini tərəfləri və oxlarına paralel olan düzbucaqlı hasarla əhatə etmək istəyir. Bu zaman hasar mümkün qədər kiçik olmalıdır, lakin bütün inəkləri əhatə etməlidir; inəklər sərhəddə birbaşa yerləşə bilər.
Təəssüf ki, keçən rüb üzrə süd məhsuldarlığının aşağı olması səbəbindən FC qənaət etmək məcburiyyətindədir. Buna görə də, mümkünsə, hasarlanmış ərazini daha da kiçiltmək istəyir və bunu əldə etmək üçün sürüsündən bir inəyi satmağa hazırdır.
FC-yə kömək edin ki, sürüdən bir inəyi çıxardıqdan sonra, qalan n - 1 inək üçün minimal əhatəedici düzbucaqlı qurduqdan sonra əhatə edə biləcəyi minimal mümkün sahəni müəyyən etsin.
Bu məsələdə inəkləri nöqtələr, hasarı isə dörd parçadan ibarət çoxluq kimi qəbul edin (yəni, inəkləri "tərəfi 1 olan kvadratlar" kimi nəzərdən keçirməyin). Diqqət edin ki, cavab sıfır ola bilər; məsələn, bu, qalan bütün inəklər eyni şaquli və ya üfüqi düz xətt üzərində yerləşdikdə baş verir.
Nəhayət, kifayət qədər böyük ola biləcəyindən, proqramın kifayət qədər sürətli işləməsi üçün alqoritmi diqqətlə seçmək lazımdır.
Birinci sətirdə n~(3 \le n \le 50000) tam ədədi verilir. Növbəti sətirdə hər bir inəyin koordinatlarını təyin edən iki tam ədəd verilir. İnəklərin koordinatları -dən -ə qədər olan müsbət tam ədədlərdir.
FC-nin xüsusi seçilmiş bir inəyi çıxardıqdan sonra əhatə edə biləcəyi minimal sahəni bildirən tək bir tam ədəd çıxarın.
Nümunə 1