Hoàng và Vương
Đề bài
Mô tả
Hoàng và Vương là hai sinh viên xuất sắc, đã giành nhiều giải thưởng trong các kỳ thi lập trình. Hôm nay, hai bạn chơi một trò chơi với các điểm và đa giác.
Ban đầu có điểm cho trước trên mặt phẳng tọa độ, đánh số từ đến . Điểm thứ có tọa độ . Không có ba điểm nào thẳng hàng.
Ban đầu trên mặt phẳng chưa có đoạn thẳng nào. Hoàng và Vương lần lượt thay phiên nhau đi. Mỗi lượt, người chơi chọn điểm cho trước chưa được nối trực tiếp bằng một đoạn thẳng và vẽ đoạn thẳng nối hai điểm đó. Nếu một người chơi không còn nước đi hợp lệ nào thì người kia thắng. Sau lượt đi của một người, nếu người đó tạo ra một đa giác lồi có mọi đỉnh đều thuộc điểm ban đầu (mọi cạnh của đa giác đều đã được vẽ) thì người đó thắng.
Ví dụ, xét trò chơi với điểm , , , , . Sau lượt đầu, đã có các đoạn thẳng nối với , với và với .
- Ở lượt thứ , Vương nối với . Lưu ý rằng hình vuông được tạo ra (có các đỉnh , , , ) không được tính vì không phải điểm cho trước. Do đó trò chơi vẫn tiếp tục.
- Ở lượt thứ , Hoàng nối với . Lần này xuất hiện đa giác lồi mới , , , , có mọi đỉnh đều thuộc các điểm cho trước, nên trò chơi kết thúc và Hoàng thắng.
Giả sử cả Hoàng và Vương đều chơi tối ưu và Hoàng đi trước, hãy xác định người thắng.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa số nguyên : số điểm.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng tên người thắng (Hoang hoặc Vuong).
Ràng buộc
- .
- .
- .
- Các điểm đôi một phân biệt, không có ba điểm nào thẳng hàng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 0 2 2 0 2 2 |
Hoang | Hoàng vẽ một đoạn bất kỳ. Vương buộc phải vẽ một đoạn có chung đầu mút với đoạn đó, rồi Hoàng vẽ đoạn còn lại và tạo thành tam giác. |
| 2 2 0 0 1 1 4 0 0 1 0 0 1 1 1 |
Hoang Vuong |
Ví dụ bổ sung (không có trong đề gốc). Với điểm, sau khi Hoàng vẽ đoạn duy nhất thì Vương không còn nước đi nên Hoàng thắng. |
Bình luận