Problem:
 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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from heapq import heappop, heapify

N,*A = map(int,read().split())

n90 = sum(x == 90 for x in A)
if n90 - (N-n90) != 4:
    print(-1)
    exit()

x = 0
temp = list(itertools.accumulate(1 if x == 90 else -1 for x in A))
slide = temp.index(min(temp)) + 1
A = A[slide:] + A[:slide]

def F(left_node, right_node, R, depth):
    step = 1<<depth
    
    
    if not R:
        n1,n2,n3,n4 = [i for i,x in enumerate(left_node) if x is not None]
        X = [None] * N
        Y = [None] * N
        X[n1] = step; Y[n1] = 0
        X[n2] = step; Y[n2] = step
        X[n3] = 0; Y[n3] = step
        X[n4] = 0; Y[n4] = 0
        return X,Y
    r = heappop(R); l = left_node[r]
    
    ll = left_node[l]; rr = right_node[r]
    left_node[rr] = ll; right_node[ll] = rr
    left_node[l] = None; left_node[r] = None
    right_node[l] = None; right_node[r] = None
    X,Y = F(left_node,right_node,R,depth+1)
    
    
    dx = X[rr] - X[ll]; dy = Y[rr] - Y[ll]
    if dx > 0:
        Y[rr] += step
        X[l] = X[rr] - step; Y[l] = Y[ll]
        X[r] = X[l]; Y[r] = Y[rr]
    elif dx < 0:
        Y[rr] -= step
        X[l] = X[rr] + step; Y[l] = Y[ll]
        X[r] = X[l]; Y[r] = Y[rr]
    elif dy > 0:
        X[rr] -= step
        X[l] = X[ll]; Y[l] = Y[rr] - step
        X[r] = X[rr]; Y[r] = Y[l]
    elif dy < 0:
        X[rr] += step
        X[l] = X[ll]; Y[l] = Y[rr] + step
        X[r] = X[rr]; Y[r] = Y[l]
    return X,Y

R = [i for i,x in enumerate(A) if x == 270]
heapify(R)

X,Y = F(list(range(-1,N-1)),list(range(1,N))+[0],R,0)


X = X[N-slide:] + X[:N-slide] 
Y = Y[N-slide:] + Y[:N-slide] 


x_to_i = {x:i for i,x in enumerate(sorted(set(X)))}
y_to_i = {y:i for i,y in enumerate(sorted(set(Y)))}
X = [x_to_i[x] for x in X]
Y = [y_to_i[y] for y in Y]

print('\n'.join('{} {}'.format(x,y) for x,y in zip(X,Y)))