/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1500 点
問題文
以下の条件を満たす N 角形を一つ構成してください:
- 多角形は単純である。 (ノートを見てください)
- 多角形の各辺は座標軸に平行である。
- 多角形の頂点の座標は 0 以上 10^9 以下の整数である。
- 多角形の頂点は反時計回りに 1 から N まで番号がつけられている。
- i 番目の頂点の内角は a_i 度である。
解が複数通り考えられる場合は、どれを出力してもかまいません。
ノート
全ての辺が正の長さを持ち、どの二つの辺も (隣接する辺が頂点で接するのを除いて) 共通部分を持たないとき、多角形は単純であるという。
制約
- 3 ≤ N ≤ 1000
- a_i は 90 または 270
入力
入力は以下の形式で標準入力から与えられる。
N a_1 : a_N
出力
解が存在する場合は、以下の形式で出力せよ:
x_1 y_1 : x_N y_N
ここで (x_i, y_i) は i 番目の頂点の座標である。
解が存在しない場合は、 -1 と出力せよ。
入力例 1
8 90 90 270 90 90 90 270 90
出力例 1
0 0 2 0 2 1 3 1 3 2 1 2 1 1 0 1
入力例 2
3 90 90 90
出力例 2
-1
Score : 1500 points
Problem Statement
Construct an N-gon that satisfies the following conditions:
- The polygon is simple (see notes for the definition).
- Each edge of the polygon is parallel to one of the coordinate axes.
- Each coordinate is an integer between 0 and 10^9, inclusive.
- The vertices are numbered 1 through N in counter-clockwise order.
- The internal angle at the i-th vertex is exactly a_i degrees.
In case there are multiple possible answers, you can output any.
Notes
A polygon is called simple if each edge has a positive length, and no two edges have a common point (except for adjacent edges touching at a vertex).
Constraints
- 3 ≤ N ≤ 1000
- a_i is either 90 or 270.
Input
The input is given from Standard Input in the following format:
N a_1 : a_N
Output
In case the answer exists, print the answer in the following format:
x_1 y_1 : x_N y_N
Here (x_i, y_i) are the coordinates of the i-th vertex.
In case the answer doesn't exist, print a single -1.
Sample Input 1
8 90 90 270 90 90 90 270 90
Sample Output 1
0 0 2 0 2 1 3 1 3 2 1 2 1 1 0 1
Sample Input 2
3 90 90 90
Sample Output 2
-1