Problem
Những con bò của nông dân John ở các điểm khác nhau (x1,y1)…(xn,yn ) các trường của nó (1≤N≤100,000, tất cả xi và yi là các số nguyên dương lẻ không vượt quá 1.000.000. FD muốn chia trường của mình bằng một hàng rào vô hạn chiều dài từ bắc xuống nam, được biểu diễn bởi phương trình x=a (a là số nguyên chẵn nên đảm bảo hàng rào không đi qua vị trí của bất kỳ con bò nào). Anh ấy cũng muốn xây một hàng rào dài vô hạn từ đông sang tây, được mô tả bằng phương trình y=b, trong đó b là một số nguyên chẵn. Hai hàng rào này cắt nhau tại (a,b) và cùng nhau chia trường thành bốn vùng.
FD muốn chọn a và b theo cách sao cho chúng được "cân bằng" số lượng bò ở tất cả các vùng, tức là để không có khu vực nào chứa quá nhiều bò. Gọi M là số bò tối đa trong 4 vùng này, FD muốn M càng nhỏ càng tốt. Giúp FD xác định giá trị tối thiểu có thể này cho M.
ĐỊNH DẠNG ĐẦU VÀO:
Dòng đầu tiên chứa một số nguyên N. Mỗi dòng trong số n dòng tiếp theo chứa vị trí của một con bò, được biểu thị bằng tọa độ x và y của nó.
ĐỊNH DẠNG ĐẦU RA:
In ra giá trị nhỏ nhất có thể của M có thể đạt được PD với cách sắp xếp hàng rào tối ưu.
|
Nhập |
Đầu ra |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |