Vật cản đường ngắm laser
Đề bài
Mô tả
Tại đài quan sát trung tâm của Khu vực 2026, hai drone trinh sát tự hành, Unit-M và Unit-L, đang thực hiện các bài kiểm tra hiệu chuẩn quang học. Trên sàn quan sát (được mô hình hóa như một mặt phẳng tọa độ Descartes 2 chiều), có nút phát hồng ngoại và đèn hiệu thu quang học nằm rải rác tại các tọa độ phân biệt.
Unit-M phải neo đậu tại một trong nút phát hồng ngoại, còn Unit-L phải neo đậu tại một trong đèn hiệu thu quang học. Để thiết lập một liên kết quang lượng tử an toàn, đường ngắm trực tiếp (đoạn thẳng nối Unit-M và Unit-L) phải hoàn toàn không bị che khuất.
Tuy nhiên, trong phòng có một cột chắn bức xạ hình trụ khổng lồ. Mặt cắt ngang của cột được biểu diễn bởi một hình tròn (tính cả phần bên trong) có tâm tại tọa độ và bán kính . Mọi nút phát và đèn hiệu thu đều nằm hẳn bên ngoài hình tròn này.
Các drone có kích thước siêu nhỏ, nên vị trí của chúng được coi là các điểm trùng với nút mà chúng neo đậu. Hai drone đã neo đậu có thể thiết lập một liên kết quang hợp lệ khi và chỉ khi đoạn thẳng nối chúng không cắt và không chạm vào hình tròn của cột chắn. Các nút phát và đèn hiệu khác không che khuất đường ngắm laser.
Hãy xác định tổng số cặp phân biệt (một nút phát cho Unit-M và một đèn hiệu thu cho Unit-L) cho phép một đường ngắm quang học không bị che khuất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (): số nút phát hồng ngoại và số đèn hiệu thu quang học.
- Dòng thứ hai chứa ba số nguyên , và (; ): tọa độ tâm và bán kính của cột chắn.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (): tọa độ của một nút phát hồng ngoại.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (): tọa độ của một đèn hiệu thu quang học.
Tất cả vị trí đôi một phân biệt. Mọi nút đều nằm hẳn bên ngoài hình tròn của cột và cách biên của nó ít nhất . Dữ liệu đảm bảo rằng dịch chuyển hai nút bất kỳ một khoảng cách Euclid không quá theo hướng bất kỳ sẽ không làm thay đổi việc đoạn thẳng nối chúng có cắt hoặc chạm vào cột hay không.
Dữ liệu ra
In ra một số nguyên duy nhất: số cặp (nút phát, đèn hiệu thu) hợp lệ có đường ngắm quang học không bị che khuất.
Ràng buộc
- .
- ; .
- với mọi nút.
- vị trí đôi một phân biệt, mọi nút nằm hẳn bên ngoài hình tròn và cách biên ít nhất .
- Dịch chuyển hai nút bất kỳ không quá không làm thay đổi việc đoạn thẳng nối chúng có cắt hoặc chạm vào cột hay không.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 0 0 2 -4 3 4 3 0 -4 -4 -3 4 -3 0 4 |
6 | Cột có tâm , bán kính . Ba cặp bị chặn là với , với và với (các đoạn thẳng đi qua tâm). Sáu cặp còn lại hợp lệ. |
| 1 2 2 -1 3 5 0 5 2 -2 -1 |
1 | Cột có tâm , bán kính . Đường thẳng tiếp xúc với cột tại , nhưng điểm này không thuộc đoạn từ tới , nên cặp này hợp lệ. Đoạn từ tới đi xuyên qua cột. |
| 1 1 0 0 1 -2 0 2 0 |
0 | Đoạn thẳng duy nhất đi qua tâm cột nên bị chặn. |
Bình luận