ATM Gạo
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Trong những ngày giãn cách xã hội, Đại học kinh tế quốc dân có cây ATM gạo để trợ giúp những người gặp khó khăn trong cuộc sống. Tuy nhiên rất nhiều người tham lam, dù giàu có vẫn đến lấy gạo miễn phí hay đến lấy nhiều lần.
Tuy nhiên, đã có 1 sáng kiến được đưa ra: chụp ảnh, sau đó nhận dạng những người đến lấy gạo. Có thể coi sân trường là một mặt phẳng tọa độ với điểm - chụp \(n\) người. Điểm thứ \(i\) có tọa độ \((x_i, y_i)\).
Hãy tìm cách chụp ảnh một số ít lần nhất điểm đã cho thỏa mãn:
- Mỗi bức ảnh có dạng một hình chữ nhật.
- Một cạnh của hình chữ nhật nằm trên trục \(Ox\).
- Diện tích của mỗi hình chữ nhật là dương nhưng không được vượt quá \(A\).
- Các hình chữ nhật có thể phủ chồng lên nhau.
Input
- Dòng đầu tiên chứa hai số nguyên dương \(n, A\) \((1 \le n \le 100; 1\le A \le 200000)\).
- \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \((x_i,y_i)\) mô tả tọa độ của điểm thứ \(i\) \((1 \le x_i \le 3.10^6; 1\le y_i \le A)\).
Output
- In ra số ít nhất các hình chữ nhật tìm được.
Example
Test 1
Input
6 4
2 1
4 1
5 1
5 4
7 1
6 4 Output
3Note
Bình luận
Bài này siêu khó luôn 😢
Anh ơi với 2 năm cống hiến LQDOJ tại acc hoangphucnguyen của em, thì em rất muốn trở thành 1 problem setter để cống hiến thêm cho LQDOJ. Đó cũng là ước mơ khi em mới vào LQDOJ của em, tuy còn non trẻ trong nghành IT nhưng em vẫn muốn được trở thành 1 problem setter, được nhận được sự dạy bảo của các bậc thánh nhân. Mong anh cho em làm problem setter của LQDOJ ạ