← 返回题目列表

AtCoder · icpc2015summer_day3_f

F. 简单感觉的人物

中文机器翻译题面 查看原题

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

Figures Of Simple Sense - 原题 PDF
赛事原始英文题册页面
可复制的 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