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ạ độ , 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:
- ưu tiên máy bay gần trung tâm hơn so với máy bay xa hơn;
- 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 );
- nếu hai máy bay cách trung tâm bằng nhau và có cùng tung độ , nó ưu tiên máy bay nằm xa hơn về phía đông (chiều dương trục ).
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 mà nó đang giám sát và hai điểm , 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 , trên biên. là bốn máy bay. Trong ví dụ này, máy bay và mỗi chiếc được đúng một trung tâm giám sát, máy bay được cả hai trung tâm giám sát, còn máy bay 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 () và () lần lượt là số máy bay và số trung tâm kiểm soát. Mỗi dòng trong dòng tiếp theo chứa hai số thực là toạ độ của một máy bay. Mỗi dòng trong dòng tiếp theo mô tả một trung tâm, gồm một số nguyên trong đoạn 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ạ độ của hai điểm , 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 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ố .
Dữ liệu ra
Với mỗi bộ dữ liệu, tính số máy bay được trung tâm giám sát, số máy bay được trung tâm giám sát, ..., số máy bay được trung tâm giám sát. In Trial cùng số thứ tự của bộ dữ liệu (bắt đầu từ ) và dấu hai chấm, tiếp theo là dãy số nguyên, trong đó số thứ là số máy bay được đúng 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
- , , .
- Mọi toạ độ là số thực có giá trị tuyệt đối không quá và có tối đa 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; và , không trùng vị trí máy bay nào.
- Một trung tâm có thì vùng kiểm soát có bán kính , không thể đi qua hai điểm phân biệt , : 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 và 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 không thẳng hàng với , : đường tròn đi qua , , có bán kính không quá , 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 .
- 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á 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 giám sát và ; tâm và tâm đều giám sát và . Vùng thứ nhất chứa máy bay xa nhất về phía bắc nên được chọn. Trung tâm 2 chỉ có một vùng khả dĩ, tâm , giám sát và . Máy bay không được giám sát, được giám sát hai lần. Bộ 2: 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 bán kính , bên trong có , 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à và . Trung tâm 2 có hai vùng khả dĩ: tâm giám sát , và tâm có hai máy bay , trên biên, giám sát ; chọn vùng thứ hai. Trung tâm 3 giám sát mọi máy bay trừ . Bộ 2: trung tâm 1 giám sát ; trung tâm 2 có hai vùng khả dĩ, giám sát hoặc , chọn vùng thứ hai vì xa hơn về phía đông. |
https://oj.chuyentin.pro/problem/icpcwf04_j
Bình luận