trang chủ / đề bài / icpc24_mb_j

Cảm biến

Đề bài

Mô tả

Một kẻ tấn công đang cố gắng đi từ làng A vào khu quân sự B. Tuy nhiên, giữa làng A và khu quân sự B là một thung lũng được canh gác bởi N camera cảm biến xoay được. Vùng cảm biến của mỗi cảm biến là một hình tròn biểu diễn bởi cặp (P,R), trong đó P là vị trí của cảm biến và R là bán kính cảm biến. R được đặt bằng 100 mét. Vì vậy, tùy vào vị trí các cảm biến, có thể vượt qua thung lũng một cách an toàn, tức là luôn giữ khoảng cách tới cảm biến gần nhất lớn hơn hẳn 100 mét tại mọi thời điểm.

Thung lũng là hình chữ nhật 0≤x≤L, 0≤y≤W. Làng A ở phía bên trái (cạnh x=0), khu quân sự B ở phía bên phải (cạnh x=L).

Kẻ tấn công nhờ bạn viết chương trình: cho chiều rộng W, chiều dài L của thung lũng và tọa độ mọi cảm biến, trước hết xác định kẻ tấn công có thể vượt qua thung lũng mà không bị phát hiện hay không. Nếu không thể, kẻ tấn công muốn biết số cảm biến ít nhất cần phá hủy để vượt qua thung lũng an toàn.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên L, W và N (1≤W≤50000, 1≤L≤50000, 1≤N≤250).
  • Mỗi dòng trong N dòng tiếp theo chứa hai số nguyên Xi và Yi: tọa độ của cảm biến thứ i (0≤Xi≤L, 0≤Yi≤W).

Tọa độ tính bằng mét so với thung lũng: góc tây nam của thung lũng có tọa độ (0,0), góc đông bắc có tọa độ (L,W). Đường đi qua thung lũng có thể bắt đầu ở điểm (0,ys) với 0≤ys≤W bất kỳ và kết thúc ở điểm (L,ye) với 0≤ye≤W bất kỳ; ys và ye không nhất thiết là số nguyên.

Dữ liệu ra

In ra số cảm biến ít nhất cần phá hủy để kẻ tấn công vượt qua thung lũng an toàn. Nếu kẻ tấn công có thể vượt qua mà không cần phá hủy cảm biến nào, in ra 0.

Ràng buộc

  • 1≤L,W≤50000
  • 1≤N≤250
  • 0≤Xi≤L, 0≤Yi≤W

Ví dụ

Input Output Giải thích
200 350 5
0 50
200 350
100 200
39 93
123 321
1 Ví dụ của đề gốc. Phá cảm biến (100,200) là đủ.
300 400 3
100 100
100 300
250 150
1 Ví dụ bổ sung, tính bằng lời giải mẫu. Hai cảm biến (100,100) và (100,300) cách nhau đúng 200 mét và mỗi cảm biến cách cạnh gần nó đúng 100 mét, nên chúng chặn kín thung lũng; phá một trong hai là đủ.

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