trang chủ / đề bài / icpc21_reg_h

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ó n điểm cho trước trên mặt phẳng tọa độ, đánh số từ 1 đến n. Điểm thứ i có tọa độ (xi,yi). 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 2 đ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 n đ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 5 điểm (1,1), (1,3), (2,4), (3,1), (3,3). Sau 3 lượt đầu, đã có các đoạn thẳng nối (1,3) với (2,4), (2,4) với (3,3) và (1,3) với (3,1).

  • Ở lượt thứ 4, Vương nối (1,1) với (3,3). Lưu ý rằng hình vuông được tạo ra (có các đỉnh (1,3), (2,2), (3,3), (2,4)) không được tính vì (2,2) không phải điểm cho trước. Do đó trò chơi vẫn tiếp tục.
  • Ở lượt thứ 5, Hoàng nối (3,3) với (3,1). Lần này xuất hiện đa giác lồi mới (1,3), (3,1), (3,3), (2,4), 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 t: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm:
    • Dòng đầu tiên chứa số nguyên n: số điểm.
    • n dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi.

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

  • 1≤t≤100.
  • 2≤n≤64.
  • 0≤|xi|,|yi|≤106.
  • 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 2 đ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

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