trang chủ / đề bài / icpc20_nat_l

Vòng khép kín

Đề bài

Mô tả

Trung béo và Hạnh gầy là đôi bạn thân. Cả hai đều thông minh, đáng yêu và rất giỏi toán lẫn lập trình. Một hôm, Trung béo ra một câu đố để thử thách Hạnh gầy. Trung đưa cho Hạnh một danh sách n điểm phân biệt trên mặt phẳng tọa độ và yêu cầu Hạnh vẽ một vòng khép kín nối tất cả các điểm này, thỏa mãn các điều kiện sau:

  • Vòng gồm đúng n đoạn thẳng, mỗi đoạn song song với một trục tọa độ.
  • Hai đầu mút của mỗi đoạn phải là 2 điểm trong danh sách. Ngoài hai điểm này, đoạn thẳng không được đi qua bất kỳ điểm nào khác trong danh sách.
  • Hai đoạn liên tiếp trên vòng phải vuông góc với nhau (tạo thành góc 90 độ), và chúng có đúng một điểm chung (chính là đầu mút chung của chúng).
  • Vòng phải đi qua tất cả n điểm. Điểm đầu và điểm cuối của vòng trùng nhau.
  • Vòng không được tự cắt.

Ví dụ (các điểm có tọa độ nguyên từ 1 đến 3):

  • Với 6 điểm (1,1),(1,3),(2,2),(2,3),(3,1),(3,2), vòng (1,1)→(3,1)→(3,2)→(2,2)→(2,3)→(1,3)→(1,1) là hợp lệ.
  • Với 3 điểm (1,1),(1,2),(2,1), vòng (1,1)→(2,1)→(2,2)→(1,2)→(1,1) không hợp lệ vì có đầu mút (2,2) không thuộc danh sách.
  • Với 5 điểm (1,1),(1,3),(2,2),(3,1),(3,3), vòng đi theo hình vuông (1,1)→(3,1)→(3,3)→(1,3)→(1,1) không hợp lệ vì không đi qua điểm (2,2).
  • Với 5 điểm (1,1),(1,3),(2,3),(3,1),(3,3), vòng đi theo hình vuông và qua (2,3) không hợp lệ vì hai đoạn liên tiếp (1,3)→(2,3) và (2,3)→(3,3) không vuông góc.

Hãy giúp Hạnh gầy xác định xem có thể vẽ được một vòng như vậy hay không.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương t, số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa số nguyên n, số điểm trong danh sách (1≤n≤2·105). Tổng n của tất cả các bộ dữ liệu không vượt quá 106.
  • Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên xi,yi, tọa độ của điểm thứ i (0≤|xi|,|yi|≤109). Không có hai điểm nào trùng tọa độ.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra YES nếu có thể vẽ được vòng, ngược lại in ra NO.

Ràng buộc

  • 1≤n≤2·105, tổng n không vượt quá 106.
  • 0≤|xi|,|yi|≤109, các điểm đôi một phân biệt.

Ví dụ

Input Output Giải thích
2
6
1 1
1 3
2 2
2 3
3 1
3 2
3
1 1
1 2
2 1
YES
NO
Bộ thứ nhất là ví dụ hợp lệ ở trên. Bộ thứ hai: muốn khép vòng phải dùng thêm đầu mút (2,2) không thuộc danh sách.
2
5
1 1
1 3
2 2
3 1
3 3
5
1 1
1 3
2 3
3 1
3 3
NO
NO
Bộ thứ nhất: điểm (2,2) không thể nằm trên vòng. Bộ thứ hai: điểm (2,3) chỉ có thể nằm giữa hai đoạn nằm ngang, không vuông góc.

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