trang chủ / đề bài / icpcwf20_f

Đườ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 0, 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 độ (x,y) 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 t là một dải nằm giữa hai đường thẳng song song cách nhau đúng t (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 n và t, trong đó n (3≤n≤3000) là số điểm và t (0≤t≤109) là độ dày của cây bút chì.

Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên x và y (−109≤x,y≤109) 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 tăng hoặc giảm 10−2, 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 t.

Ràng buộc

  • 3≤n≤3000; 0≤t≤109.
  • −109≤x,y≤109; 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 tăng hoặc giảm 10−2.

Ví dụ

Input Output Giải thích
4 2
0 0
2 4
4 9
3 1
3 Ba điểm (0,0), (2,4), (4,9) nằm trong một dải rộng 2: điểm (2,4) chỉ cách đường thẳng qua (0,0) và (4,9) khoảng 0,2. Không dải rộng 2 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à 2 (từ (1000,12) xuống cạnh nối hai điểm còn lại), lớn hơn t=1.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0