trang chủ / đề bài / icpcwf04_j

Kiểm soát không lưu

Đề bài

Mô tả

Để tránh va chạm trên không, hầu hết các chuyến bay thương mại đều được các trung tâm kiểm soát không lưu mặt đất theo dõi, dùng radar để xác định vị trí máy bay. Trong bài này, bạn được cho thông tin về một tập máy bay và một tập trung tâm kiểm soát, và cần tính xem việc giám sát các máy bay được phân chia giữa các trung tâm như thế nào. Vị trí mỗi máy bay được biểu diễn bởi một cặp toạ độ (x,y), hai máy bay khác nhau có vị trí khác nhau. Trong bài này bỏ qua độ cao của máy bay.

Số máy bay mà một trung tâm có thể giám sát thay đổi theo thời gian do thay đổi về nhân sự và thiết bị. Tại mỗi thời điểm, mỗi trung tâm giám sát nhiều máy bay nhất có thể, chọn máy bay theo thứ tự ưu tiên sau:

  1. ưu tiên máy bay gần trung tâm hơn so với máy bay xa hơn;
  2. nếu hai máy bay cách trung tâm bằng nhau và trung tâm chỉ còn giám sát được một trong hai, nó chọn máy bay nằm xa hơn về phía bắc (chiều dương trục y);
  3. nếu hai máy bay cách trung tâm bằng nhau và có cùng tung độ y, nó ưu tiên máy bay nằm xa hơn về phía đông (chiều dương trục x).

Tại mỗi thời điểm, mỗi trung tâm có một "vùng kiểm soát" hình tròn có tâm là trung tâm đó và bán kính bằng khoảng cách tới máy bay xa nhất mà nó đang giám sát. Mọi máy bay nằm bên trong vùng kiểm soát đều được trung tâm giám sát. Máy bay nằm trên biên của vùng kiểm soát có thể được hoặc không được giám sát, tuỳ theo khả năng của trung tâm và thứ tự ưu tiên ở trên.

Bạn không được cho vị trí của các trung tâm. Thay vào đó, với mỗi trung tâm, bạn được cho số máy bay k mà nó đang giám sát và hai điểm A, B nằm trên biên của vùng kiểm soát hiện tại của nó. Từ thông tin này có thể tính được vị trí của trung tâm và xác định nó đang giám sát những máy bay nào. Nếu dữ liệu phù hợp với nhiều vùng kiểm soát khả dĩ, hãy chọn vùng chứa máy bay nằm xa nhất về phía bắc, nếu bằng nhau thì xét máy bay xa nhất về phía bắc rồi xa nhất về phía đông. Cụ thể: với mỗi vùng khả dĩ, xét máy bay xa nhất về phía bắc trong các máy bay mà vùng đó giám sát (nếu có nhiều máy bay cùng tung độ lớn nhất thì lấy máy bay xa nhất về phía đông); chọn vùng có máy bay này nằm xa nhất về phía bắc, nếu cùng tung độ thì xa nhất về phía đông.

Hình dưới đây (minh hoạ, không theo tỉ lệ) gồm bốn máy bay và hai trung tâm. Mỗi trung tâm được biểu diễn bởi vùng kiểm soát hình tròn và hai điểm A, B trên biên. P1,P2,P3,P4 là bốn máy bay. Trong ví dụ này, máy bay P1 và P4 mỗi chiếc được đúng một trung tâm giám sát, máy bay P3 được cả hai trung tâm giám sát, còn máy bay P2 không được trung tâm nào giám sát.

Dữ liệu vào

Dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên của mỗi bộ chứa hai số nguyên NP (0<NP<100) và NC (0<NC<10) lần lượt là số máy bay và số trung tâm kiểm soát. Mỗi dòng trong NP dòng tiếp theo chứa hai số thực là toạ độ (x,y) của một máy bay. Mỗi dòng trong NC dòng tiếp theo mô tả một trung tâm, gồm một số nguyên k trong đoạn [0,NP] là số máy bay mà trung tâm đang giám sát, tiếp theo là hai cặp số thực là toạ độ (x,y) của hai điểm A, B trên biên vùng kiểm soát của nó (không điểm nào trong hai điểm này trùng với vị trí một máy bay). Nếu hai khoảng cách chênh nhau ít hơn 0,00001 thì coi như chúng bằng nhau.

Sau bộ dữ liệu cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ dữ liệu, tính số máy bay được 0 trung tâm giám sát, số máy bay được 1 trung tâm giám sát, ..., số máy bay được NC trung tâm giám sát. In Trial cùng số thứ tự của bộ dữ liệu (bắt đầu từ 1) và dấu hai chấm, tiếp theo là dãy NC+1 số nguyên, trong đó số thứ i là số máy bay được đúng i−1 trung tâm giám sát. Nếu dữ liệu của một trung tâm nào đó mâu thuẫn (không có vùng kiểm soát nào phù hợp), in Impossible thay cho dãy số của bộ dữ liệu đó. In theo định dạng ở ví dụ và in một dòng trống sau mỗi bộ dữ liệu.

Ràng buộc

  • 0<NP<100, 0<NC<10, 0≤k≤NP.
  • Mọi toạ độ là số thực có giá trị tuyệt đối không quá 1000 và có tối đa 2 chữ số sau dấu chấm thập phân.
  • Các máy bay có vị trí đôi một khác nhau; A≠B và A, B không trùng vị trí máy bay nào.
  • Một trung tâm có k=0 thì vùng kiểm soát có bán kính 0, không thể đi qua hai điểm phân biệt A, B: dữ liệu của trung tâm đó mâu thuẫn. (Ngoài ra, dữ liệu bảo đảm mọi đường tròn đi qua A và B của trung tâm đó đều chứa ít nhất một máy bay nằm hẳn bên trong.)
  • Với mỗi trung tâm và mỗi máy bay P không thẳng hàng với A, B: đường tròn đi qua A, B, P có bán kính không quá 105, và mọi máy bay hoặc nằm đúng trên đường tròn đó, hoặc có khoảng cách tới tâm chênh với bán kính ít nhất 10−3.
  • Khi có nhiều vùng kiểm soát khả dĩ, vùng được chọn theo quy tắc ở trên là duy nhất.
  • Mỗi file có không quá 100 bộ dữ liệu.

Ví dụ

Input Output Giải thích
4 2
3.0 0.0
0.0 0.0
1.6 2.8
2.0 1.0
2 1.0 2.0 2.0 0.0
2 2.0 2.0 4.0 2.0
2 1
0.0 0.5
0.0 -0.5
0 -1.0 0.0 1.0 0.0
0 0
Trial 1: 1 2 1

Trial 2: Impossible
Bộ 1, trung tâm 1 có ba vùng khả dĩ: tâm (2,5; 1,5) giám sát (2,1) và (1,6; 2,8); tâm (1; 0,75) và tâm (0,5; 0,5) đều giám sát (2,1) và (0,0). Vùng thứ nhất chứa máy bay xa nhất về phía bắc (1,6; 2,8) nên được chọn. Trung tâm 2 chỉ có một vùng khả dĩ, tâm (3; 1,25), giám sát (2,1) và (3,0). Máy bay (0,0) không được giám sát, (2,1) được giám sát hai lần. Bộ 2: k=0 nên dữ liệu mâu thuẫn.
6 3
0.0 0.0
3.0 4.0
-3.0 4.0
5.0 0.0
0.0 -5.0
10.0 10.0
3 4.0 -3.0 -4.0 -3.0
1 -1.0 1.0 1.0 1.0
5 -20.0 0.0 20.0 0.0
3 2
0.0 0.0
1.0 0.0
2.0 0.0
1 -1.0 1.0 3.0 1.0
2 0.5 0.5 0.5 -0.5
0 0
Trial 1: 1 2 2 1

Trial 2: 1 1 1
Ví dụ tự thêm. Bộ 1: trung tâm 1 có vùng tâm (0,0) bán kính 5, bên trong có (0,0), trên biên có bốn máy bay; hai máy bay còn lại được chọn theo ưu tiên phía bắc rồi phía đông là (3,4) và (−3,4). Trung tâm 2 có hai vùng khả dĩ: tâm (0,1) giám sát (0,0), và tâm (0; 23/6) có hai máy bay (3,4), (−3,4) trên biên, giám sát (3,4); chọn vùng thứ hai. Trung tâm 3 giám sát mọi máy bay trừ (10,10). Bộ 2: trung tâm 1 giám sát (1,0); trung tâm 2 có hai vùng khả dĩ, giám sát {(0,0),(1,0)} hoặc {(1,0),(2,0)}, chọn vùng thứ hai vì (2,0) xa hơn về phía đông.

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