Cân Bằng Tải

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $N$ điểm trên mặt phẳng, tọa độ của mỗi điểm là các số nguyên dương lẻ không vượt quá $10^{6}$ . Cần đặt hai đường thẳng phân chia: một đường thẳng đứng $x = a$ và một đường thẳng nằm ngang $y = b$ , trong đó $a, b$ là các số nguyên chẵn dương. Hai đường thẳng này chia mặt phẳng thành 4 góc phần tư (Tây Bắc, Đông Bắc, Tây Nam, Đông Nam).

Hãy chọn $a$ và $b$ sao cho số điểm lớn nhất trong bất kỳ góc phần tư nào là nhỏ nhất có thể.

Điểm nằm trên đường thẳng không tồn tại vì tọa độ điểm lẻ còn $a, b$ chẵn.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 100000$ ).
$N$ dòng tiếp theo: mỗi dòng gồm hai số nguyên lẻ $x_{i}$ , $y_{i}$ ( $1 \leq x_{i}, y_{i} \leq 10^{6}$ ) — tọa độ của điểm thứ $i$ .

Dữ liệu ra

Một số nguyên duy nhất — số điểm lớn nhất trong một góc phần tư khi chọn $a, b$ tối ưu.

Ràng buộc

$1 \leq N \leq 100000$
$1 \leq x_{i}, y_{i} \leq 10^{6}$ , $x_{i}$ và $y_{i}$ đều là số lẻ.

Ví dụ

Input	Output	Giải thích
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2	Đặt $a = 6$ , $b = 4$ : góc Tây Nam có {(5,3),(3,1)} = 2 điểm; góc Tây Bắc có {(5,5),(7,13)} = 2 điểm; góc Đông Nam có {(7,3),(9,1)} = 2 điểm; góc Đông Bắc có {(7,13)... } = 1 điểm. Không thể làm tốt hơn 2.

Ghi chú

Đảm bảo $a$ và $b$ là số chẵn dương nên không có điểm nào nằm đúng trên đường phân chia.

Bình luận

Không có bình luận tại thời điểm này.