trang chủ / đề bài / icpc22_reg_g

Công nghệ goal-line

Đề bài

Mô tả

World Cup 2022 đang diễn ra tại Qatar. Năm nay, rất nhiều công nghệ mới được dùng để hỗ trợ trọng tài loại bỏ phần lớn các quyết định gây tranh cãi.

Người hâm mộ Anh sẽ không bao giờ quên sự cố trong trận đấu với Đức năm 2010. Cú sút của Frank Lampard đã đưa bóng vượt qua vạch vôi khung thành nhưng trọng tài không nhận ra và không công nhận bàn thắng cho đội tuyển Anh. Sự cố này cũng dẫn tới việc phát triển công nghệ goal-line. Công nghệ này xác định liệu toàn bộ quả bóng đã vượt qua vạch vôi khung thành hay chưa.

Hệ thống gồm 14 camera tốc độ cao gắn quanh sân vận động. Các camera theo dõi quả bóng với độ chính xác cao và dùng phép đo tam giác để tính vị trí chính xác của bóng so với vạch vôi. Phép đo tam giác là kỹ thuật hình học tính khoảng cách tới và vị trí của một điểm chưa biết nhờ hai điểm đã biết: hệ thống tạo một tam giác giữa ba điểm này và dùng các góc giữa chúng để xác định vị trí điểm thứ ba. Phần mềm của hệ thống sau đó dựng hình ảnh 3D của quả bóng so với vạch vôi.

Luật bóng đá quy định:

Bàn thắng được ghi khi toàn bộ quả bóng đi qua vạch vôi khung thành, ở giữa hai cột dọc và dưới xà ngang, với điều kiện đội ghi bàn không phạm lỗi.

Về mặt toán học, xét hình chiếu từ trên xuống của quả bóng và khung thành. Quả bóng là một hình tròn B. Vạch vôi là miền S giới hạn bởi hai đường thẳng song song x=x1 và x=x2 (x1≠x2). Hai đường thẳng này chia mặt phẳng thành 3 phần:

  • Vạch vôi là miền nằm giữa hai đường thẳng;
  • Phía trong khung thành là miền kề với đường thẳng x=x1 (nằm ở phía bên kia của x=x1 so với vạch vôi);
  • Phần còn lại là phía trong sân.

Bàn thắng được ghi nếu có một thời điểm quả bóng nằm hoàn toàn trong phía trong khung thành. Nói cách khác, các điều kiện sau đều thỏa mãn:

  • Phần chung của B và vạch vôi có diện tích bằng 0;
  • Phần chung của B và phía trong sân có diện tích bằng 0.

Trong bài này, ta chỉ quan tâm tới vị trí tương đối của quả bóng so với vạch vôi, nên chỉ xét tọa độ x và bỏ qua tọa độ y và z. Chuyển động của quả bóng được 14 camera ghi lại trong một số khung hình, cho ra danh sách n tọa độ p1,p2,…,pn, trong đó pi là tọa độ x của tâm quả bóng ở khung hình thứ i.

Cho danh sách p, bán kính r của quả bóng và vị trí của vạch vôi, hãy xác định đó có phải là bàn thắng hay không.

Dữ liệu vào

  • Dòng đầu tiên gồm 4 số nguyên n, r, x1, x2 (1≤n≤104, 1≤r≤111, |x1|≤106, |x2|≤106, x1≠x2).
  • Dòng thứ hai gồm n số nguyên p1,p2,…,pn (|pi|≤106).

Dữ liệu ra

In ra GOAL nếu đó là bàn thắng, ngược lại in ra NO GOAL.

Ràng buộc

  • 1≤n≤104
  • 1≤r≤111
  • |x1|,|x2|≤106, x1≠x2
  • |pi|≤106

Ví dụ

Input Output Giải thích
6 10 120 110
90 100 110 120 130 140
GOAL Quả bóng lăn chậm vào khung thành. Phía trong khung thành là x≥120; ở khung hình thứ 5, quả bóng chiếm đoạn [120,140], nằm hoàn toàn trong khung thành (chạm vạch x=120 vẫn được tính).
8 10 0 10
10 4 -2 -8 -1 5 10 15
NO GOAL Quả bóng lăn về phía khung thành trống nhưng một hậu vệ đã phá bóng xuất sắc. Phía trong khung thành là x≤0, nhưng tâm bóng chỉ tới −8, nên bóng luôn còn chạm vạch vôi.
1 1 2 3
1
GOAL Quả bóng không di chuyển nhưng nằm trong khung thành: nó chiếm đoạn [0,2], còn phía trong khung thành là x≤2.

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