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 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 , trong đó là vị trí của cảm biến và là bán kính cảm biến. được đặt bằng 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 mét tại mọi thời điểm.
Thung lũng là hình chữ nhật , . Làng A ở phía bên trái (cạnh ), khu quân sự B ở phía bên phải (cạnh ).
Kẻ tấn công nhờ bạn viết chương trình: cho chiều rộng , chiều dài 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 , và (, , ).
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và : tọa độ của cảm biến thứ (, ).
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 độ , góc đông bắc có tọa độ . Đường đi qua thung lũng có thể bắt đầu ở điểm với bất kỳ và kết thúc ở điểm với bất kỳ; và 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 .
Ràng buộc
- ,
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 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 và cách nhau đúng mét và mỗi cảm biến cách cạnh gần nó đúng mét, nên chúng chặn kín thung lũng; phá một trong hai là đủ. |
Bình luận