Giám sát
Đề bài
Mô tả
Tập đoàn Quốc tế về Bảo vệ và Kiểm soát (ICPC) phát triển những công nghệ hiệu quả cho, ừm, việc bảo vệ và kiểm soát. Dĩ nhiên, họ rất muốn chính trụ sở của mình cũng được bảo vệ và kiểm soát.
Nhìn từ trên xuống, tòa nhà trụ sở có dạng một đa giác lồi. Xung quanh tòa nhà có một số vị trí thích hợp để lắp camera giám sát. Tùy theo vị trí, mỗi camera quan sát được một dãy các cạnh của đa giác (các bức tường của tòa nhà). ICPC muốn dùng ít camera nhất có thể để quan sát được toàn bộ tòa nhà.
Dữ liệu vào
Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên và : là số bức tường và là số vị trí có thể lắp camera. Các bức tường được đánh số từ đến theo thứ tự quanh tòa nhà.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và cho biết camera đặt ở vị trí thứ quan sát được những bức tường nào:
- Nếu thì camera quan sát mọi bức tường với .
- Nếu thì camera quan sát mọi bức tường với hoặc .
Dữ liệu ra
In ra số camera ít nhất đủ để quan sát được mọi bức tường của tòa nhà. Vùng quan sát của hai camera được phép chồng lên nhau. Nếu không thể quan sát toàn bộ tòa nhà, in ra impossible.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 100 7 1 50 50 70 70 90 90 40 20 60 60 80 80 20 |
3 | Ba camera , , quan sát lần lượt các bức tường và , , , phủ kín cả bức tường. Không có hai camera nào đủ. |
| 8 2 8 3 5 7 |
impossible | Bức tường không được camera nào quan sát. |
| 8 2 8 4 5 7 |
2 | Camera quan sát các bức tường , camera quan sát . |
Bình luận