trang chủ / đề bài / icpc26_mb_h

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 nút phát hồng ngoại và M đè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 nút phát hồng ngoại, còn Unit-L phải neo đậu tại một trong M đè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 độ (xc,yc) và bán kính r. 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 N và M (1≤N,M≤105): 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 xc, yc và r (|xc|,|yc|≤104; 1≤r≤104): tọa độ tâm và bán kính của cột chắn.
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi (|xi|,|yi|≤104): tọa độ của một nút phát hồng ngoại.
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi (|xi|,|yi|≤104): tọa độ của một đèn hiệu thu quang học.

Tất cả N+M 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 10−6. 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á 10−6 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

  • 1≤N,M≤105.
  • |xc|,|yc|≤104; 1≤r≤104.
  • |xi|,|yi|≤104 với mọi nút.
  • N+M 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 10−6.
  • Dịch chuyển hai nút bất kỳ không quá 10−6 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 (0,0), bán kính 2. Ba cặp bị chặn là (−4,3) với (4,−3), (4,3) với (−4,−3) và (0,−4) với (0,4) (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 (2,−1), bán kính 3. Đường thẳng x=5 tiếp xúc với cột tại (5,−1), nhưng điểm này không thuộc đoạn từ (5,0) tới (5,2), nên cặp này hợp lệ. Đoạn từ (5,0) tới (−2,−1) đ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

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