Module: Carian ternary

Lembu Farmer John berada di titik yang berbeza (x₁,y₁)…(x_n,y_n ) medannya (1≤N≤100,000, semua x_i dan y_i ialah integer ganjil positif tidak melebihi 1,000,000. FD ingin membahagikan bidangnya dengan pagar tak terhingga panjang dari utara ke selatan, diterangkan oleh persamaan x=a (a ialah integer genap, jadi dipastikan pagar itu tidak melepasi kedudukan mana-mana lembu.) Dia juga ingin membina pagar dengan panjang tidak terhingga dari timur ke barat, yang diterangkan oleh persamaan y=b, dengan b ialah integer genap Kedua-dua pagar ini bersilang di (a,b), dan bersama-sama membahagikan medan kepada empat kawasan.

FD mahu memilih a dan b supaya mereka mendapat "seimbang" bilangan lembu di semua wilayah, i.e. supaya tidak ada kawasan yang mengandungi terlalu banyak lembu. Biarkan M menjadi bilangan maksimum lembu di empat wilayah ini, FD mahu M menjadi sekecil mungkin. Bantu FD menentukan nilai kemungkinan minimum ini untuk M.

 

FORMAT INPUT:

Baris pertama input mengandungi satu integer, N. Setiap baris n seterusnya mengandungi lokasi satu lembu, ditunjukkan oleh koordinat x dan ynya.

FORMAT OUTPUT:

Cetak nilai minimum yang mungkin bagi M yang boleh mencapai PD dengan susunan pagar yang optimum.

Masukkan	Output
7 73 5 5 7 13 3 1 117 5 3 9 1	2