#446. DPPOINTS – Nối điểm đen trắng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

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.

Yêu cầu: Cho tọa độ của n điểm đen a_1, a_2, …, a_N và tọa độ của n đ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.

Dữ liệu vào:

  • Dòng thứ nhất chứa số nguyên dương n ;
  • Dòng thứ hai chứa các số a_1, a_2, …, a_N ;
  • Dòng thứ ba chứa các số b_1, b_2, …, b_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.

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số k lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:
3
0 3 1
-3 5 -1
Dữ liệu ra:
2
Giải thích:
Cách chọn các điểm để nối

Giới hạn:

  • 1 ≤ N ≤ 10^5; |a_i|, |b_i| ≤ 10^9 .