AtCoder 图片原名已被搁置;此后,原始图像取自英语原文,现已完整保存。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem F. Figures Of Simple Sense
Input le: foss.in
Output le: foss.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that drawing polygons is easy? This is not the case when you have some restrictions.
In this problem all you have to do is just to draw a polygon. It must have exactly N vertices. It
must contain no self-intersections. No three consecutive vertices of the polygon must be collinear.
All coordinates of its vertices must be integers between 0 and 10 000, inclusive. Easy, right?
There is one more small restriction though. The number of inner angles of this polygon equal to
90◦must be as large as possible under these constraints. What do you think about it now?
Input
The input le contains the number of test cases T (1 ≤T ≤30) followed by T integer numbers
N (3 ≤N ≤1000).
Output
For each test case, output the maximum possible number of inner angles equal to 90◦followed
by N pairs of integers the coordinates of the vertices of the polygon in either clockwise or
counterclockwise order. Of course, more than one solution is possible, so output any of them.
Examples
foss.in foss.out
2 4
4 0 0
6 1 0
1 1
0 1
5
1 1
3 3
5 1
4 0
3 1
2 0
Page 6 of 10