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 đ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 đ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à đ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 độ), 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ả đ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ừ đến ):
- Với điểm , vòng là hợp lệ.
- Với điểm , vòng không hợp lệ vì có đầu mút không thuộc danh sách.
- Với điểm , vòng đi theo hình vuông không hợp lệ vì không đi qua điểm .
- Với điểm , vòng đi theo hình vuông và qua không hợp lệ vì hai đoạn liên tiếp và 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 , số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa số nguyên , số điểm trong danh sách (). Tổng của tất cả các bộ dữ liệu không vượt quá .
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên , tọa độ của điểm thứ (). 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
- , tổng không vượt quá .
- , 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 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 không thể nằm trên vòng. Bộ thứ hai: điểm chỉ có thể nằm giữa hai đoạn nằm ngang, không vuông góc. |
Bình luận