VOI 11 Bài 4 - Nối điểm đen trắng

Xem dạng PDF

Gửi bài giải


Điểm: 0,09 (OI)
Giới hạn thời gian: 0.6s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOI 2011
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên trục số thực cho ~n~ điểm đen và ~n~ điểm trắng hoàn toàn phân biệt. Các điểm đen có tọa độ nguyên ~a_1, a_2, ..., a_n~ còn các điểm trắng có tọa độ nguyên ~b_1, b_2, ..., b_n~. Người ta muốn chọn ra ~k~ điểm đen và ~k~ điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho ~k~ đoạn thẳng tạo được đôi một không có điểm chung.

Kết quả: Ghi ra một số nguyên duy nhất là số ~k~ lớn nhất tìm được

Input

  • Dòng thứ nhất chứa số nguyên dương ~n\; (n \leq 10^5)~.
  • Dòng thứ hai chứa các số ~a_1, a_2, ..., a_n\; (|a_i| \leq 10^9, i = 1, 2,..., n)~.
  • Dòng thứ ba chứa các số ~b_1, b_2, ..., b_n\; (|b_i| \leq 10^9, i = 1, 2,..., n)~.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Cho tọa độ của ~n~ điểm đen ~a_1, a_2, ..., a_n~ và tọa độ của điểm trắng ~b_1, b_2, ..., b_n~. Hãy tìm giá trị ~k~ lớn nhất thỏa mãn yêu cầu trên.

Giới hạn

50% số test ứng với 50% số điểm của bài có ~1 \leq n \leq 100~

Sample Input

3
0 3 1
-3 5 -1

Sample Output

2

Note

image


Bình luận

Hãy đọc nội quy trước khi bình luận.


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