|School Personal Contest #2 (Winter Computer School 2010/11)
Codeforces Beta Round #43 (ACM-ICPC Rules)
It happened at the times of the Great Berland Empire. Once the Emperor dreamt that the Messenger from the gods ordered to build a temple whose base would be a convex polygon with n angles. Next morning the Emperor gave the command to build a temple whose base was a regular polygon with n angles. The temple was built but soon the Empire was shaken with disasters and crop failures. After an earthquake destroyed the temple, the Emperor understood that he somehow caused the wrath of gods to fall on his people. He ordered to bring the wise man. When the wise man appeared, the Emperor retold the dream to him and asked "Oh the wisest among the wisest, tell me how could I have infuriated the Gods?". "My Lord," the wise man answered. "As far as I can judge, the gods are angry because you were too haste to fulfill their order and didn't listen to the end of the message".
Indeed, on the following night the Messenger appeared again. He reproached the Emperor for having chosen an imperfect shape for the temple. "But what shape can be more perfect than a regular polygon!?" cried the Emperor in his dream. To that the Messenger gave a complete and thorough reply.
You are an obedient architect who is going to make the temple's plan. Note that the polygon should be simple (having a border without self-intersections and overlapping) and convex, however, it is acceptable for three consecutive vertices to lie on the same line.
The first line contains the single number n (3 ≤ n ≤ 10000).
Print "YES" (without quotes) in the first line if it is possible to build a polygon possessing the needed qualities. In the next n lines print integer coordinates of the polygon vertices in the order in which they would be passed counter clockwise. The absolute value of the coordinates shouldn't exceed 109. No two vertices can coincide. It is permitted to print any of the possible solutions. Print "NO" if to build the polygon is impossible.