trang chủ / đề bài / icpc25_mn_i

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 n đỉ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 [−109,109].

Ngoài ra, số đường chéo nằm hoàn toàn bên trong đa giác phải đúng bằng k. Đườ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 n và k (4≤n≤100, 0≤k≤n(n−3)2).

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à n dòng, mỗi dòng chứa một cặp số nguyên xi, yi (−109≤xi,yi≤109): 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

  • 4≤n≤100
  • 0≤k≤n(n−3)2
  • Tọa độ các đỉnh in ra là số nguyên trong đoạn [−109,109]

Ví dụ

Input Output Giải thích
5 4 Yes
0 0
3 0
2 1
3 2
0 2
Đỉnh (2,1) lõm vào trong. Bốn đường chéo nằm bên trong là các đường chéo nối (2,1) với (0,0) và (0,2), nối (3,0) với (0,2), và nối (3,2) với (0,0). Đường chéo nối (3,0) với (3,2) 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 (1,1) với (0,0) và (0,2) 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

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