Đường ley
Đề bài
Mô tả
Năm 1921, nhà khảo cổ nghiệp dư Alfred Watkins đặt ra thuật ngữ "đường ley" (ley lines) để chỉ những đường thẳng nối nhiều địa điểm có ý nghĩa địa lý và lịch sử. Các đường này thường gắn với những giả thuyết bí ẩn và huyền bí, nhiều giả thuyết trong số đó vẫn còn tồn tại tới ngày nay.
Một lời chỉ trích phổ biến đối với đường ley là các đường người ta vẽ trên bản đồ thực ra có độ rộng khác , và việc tìm được "đường thẳng" nối nhiều địa điểm là chuyện tầm thường nếu các điểm đủ dày đặc và cây bút chì đủ to. Trong bài này, bạn sẽ kiểm chứng lời chỉ trích đó.
Để đơn giản, ta bỏ qua độ cong của Trái Đất và coi như đang làm việc với một tập điểm trên mặt phẳng, mỗi điểm có tọa độ riêng biệt và không có ba điểm nào cùng nằm trên một đường thẳng. Cho tập điểm đó và độ dày của cây bút chì, hỏi một "đường thẳng" vẽ bằng cây bút đó có thể đi qua nhiều nhất bao nhiêu điểm?
Nói cách khác, một "đường thẳng" có độ dày là một dải nằm giữa hai đường thẳng song song cách nhau đúng (tính cả hai đường biên). Hãy tìm số điểm lớn nhất có thể nằm trong một dải như vậy.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó () là số điểm và () là độ dày của cây bút chì.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và () là tọa độ của một điểm trong tập.
Dữ liệu đảm bảo đáp án không thay đổi nếu độ dày tăng hoặc giảm , và không có ba điểm nào thẳng hàng.
Dữ liệu ra
In ra số điểm lớn nhất nằm trên một "đường thẳng" có độ dày .
Ràng buộc
- ; .
- ; các điểm đôi một phân biệt, không có ba điểm nào thẳng hàng.
- Đáp án không đổi khi tăng hoặc giảm .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 0 0 2 4 4 9 3 1 |
3 | Ba điểm , , nằm trong một dải rộng : điểm chỉ cách đường thẳng qua và khoảng . Không dải rộng nào chứa cả bốn điểm. |
| 3 1 0 10 2000 10 1000 12 |
2 | Muốn chứa cả ba điểm, dải phải rộng ít nhất bằng chiều cao nhỏ nhất của tam giác, ở đây là (từ xuống cạnh nối hai điểm còn lại), lớn hơn . |
Bình luận