trang chủ / đề bài / icpcwf14_i

Mạng cảm biến

Đề bài

Mô tả

Mạng cảm biến không dây gồm các cảm biến tự động được rải khắp một vùng môi trường, theo dõi các điều kiện như nhiệt độ, âm thanh và áp suất.

Samantha là nhà nghiên cứu tham gia dự án Đo Carbon-dioxide ở Amazon (Amazon Carbon-dioxide Measurement, ACM). Trong dự án này, một mạng cảm biến không dây trong rừng mưa Amazon thu thập thông tin về môi trường. Rừng mưa Amazon lưu trữ một lượng carbon tương đương lượng khí thải từ nhiên liệu hóa thạch của toàn thế giới trong một thập kỷ, và giữ vai trò quan trọng trong quá trình trao đổi oxy của Trái Đất. Vì khu rừng rất rộng lớn, những thay đổi của nó không chỉ ảnh hưởng tới môi trường địa phương mà còn tới khí hậu toàn cầu, do làm thay đổi các dòng gió và dòng hải lưu. Mục tiêu của dự án ACM là giúp các nhà khoa học hiểu rõ hơn các hệ sinh thái phức tạp của Trái Đất và tác động của con người.

Samantha có một giả thuyết quan trọng. Để kiểm chứng nó, cô cần tìm một tập con các cảm biến sao cho mọi cặp cảm biến trong tập đều liên lạc trực tiếp được với nhau. Một cảm biến liên lạc trực tiếp được với mọi cảm biến khác cách nó một khoảng không quá d. Để thí nghiệm chính xác nhất có thể, Samantha muốn chọn càng nhiều cảm biến càng tốt.

Vì không thể cứ thế đi vào rừng Amazon, Samantha không thể thêm cảm biến mới hay di chuyển các cảm biến đang có. Cho vị trí hiện tại của các cảm biến, hãy giúp cô tìm tập con lớn nhất thỏa mãn yêu cầu trên. Để đơn giản, mỗi cảm biến được biểu diễn bằng một điểm trên mặt phẳng, và khoảng cách giữa hai điểm là khoảng cách Euclid thông thường.

Dữ liệu vào

Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên n và d, lần lượt là số cảm biến và khoảng cách lớn nhất giữa hai cảm biến liên lạc trực tiếp được với nhau. Các cảm biến được đánh số từ 1 tới n. Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên x và y, tọa độ của một cảm biến, bắt đầu từ cảm biến thứ nhất.

Dữ liệu ra

In ra một tập con lớn nhất các cảm biến mà mọi cặp cảm biến trong đó đều liên lạc trực tiếp được với nhau. Dòng đầu tiên in kích thước của tập con. Dòng thứ hai in chỉ số (đánh số từ 1) của các cảm biến trong tập con. Nếu có nhiều tập con như vậy, in ra một tập bất kỳ.

Ràng buộc

  • 1≤n≤100.
  • 1≤d≤10000.
  • −10000≤x,y≤10000.

Ví dụ

Input Output Giải thích
4 1
0 0
0 1
1 0
1 1
2
1 2
Bốn cảm biến ở bốn đỉnh hình vuông cạnh 1: hai đỉnh kề nhau cách nhau 1≤d, hai đỉnh đối nhau cách nhau 2>d, nên không chọn được 3 cảm biến. Các đáp án khác như 1 3 cũng đúng.
5 20
0 0
0 2
100 100
100 110
100 120
3
4 3 5
Cảm biến 3 và 5 cách nhau đúng 20. Thứ tự in các chỉ số tùy ý.

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