Vẽ đa giác
Đề bài
Mô tả
Nhiệm vụ của bạn là vẽ một đa giác đơn có đúng đỉnh. Đa giác đơn là đa giác không tự cắt, không có lỗ, và không có ba đỉnh liên tiếp nào thẳng hàng. Tọa độ các đỉnh phải là số nguyên trong đoạn .
Ngoài ra, số đường chéo nằm hoàn toàn bên trong đa giác phải đúng bằng . Đường chéo của đa giác là đoạn thẳng nối hai đỉnh không kề nhau. Một đường chéo được coi là nằm hoàn toàn bên trong nếu mọi điểm của nó, trừ hai đầu mút, đều nằm trong miền trong của đa giác (không chạm vào cạnh hay đỉnh nào của đa giác).
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và (, ).
Dữ liệu ra
Nếu không thể vẽ được đa giác như vậy, in ra một từ duy nhất No. Ngược lại, in Yes ở dòng đầu tiên, tiếp theo là dòng, mỗi dòng chứa một cặp số nguyên , (): các đỉnh của đa giác liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
Đa giác không được tự cắt hay tự chạm, không có hai đỉnh trùng nhau, và không có ba đỉnh liên tiếp nào nằm trên cùng một đường thẳng. Nếu có nhiều đáp án, in ra đáp án bất kỳ.
Ràng buộc
- Tọa độ các đỉnh in ra là số nguyên trong đoạn
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 | Yes 0 0 3 0 2 1 3 2 0 2 |
Đỉnh lõm vào trong. Bốn đường chéo nằm bên trong là các đường chéo nối với và , nối với , và nối với . Đường chéo nối với nằm ngoài đa giác. |
| 5 2 | Yes 0 0 2 0 1 1 2 2 0 2 |
Chỉ có hai đường chéo nối với và nằm bên trong. |
| 4 0 | No | Mọi tứ giác đơn đều có ít nhất một đường chéo nằm bên trong. |
Bình luận