Submission #1290936

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef pair<int,int> P;
vector<P> construct(vector<int> as){
	int N = as.size();
	if(N==4){
		vector<P> res;
		res.pb(P(1,0));
		res.pb(P(1,1));
		res.pb(P(0,1));
		res.pb(P(0,0));
		return res;
	}
	int s = -1;
	rep(i,N){
		if(as[i]==90 && as[(i+1)%N]==270) s=i;
	}
	vector<int> nas;
	for(int i=s-1;i<s-1+N;i++) if(i!=s&&i!=s+1) nas.pb(as[(i+N)%N]);
	vector<P> base = construct(nas);
	vector<P> res(N);

	rep(i,N-2){
		P p = base[i];
		if(i==0 || base[0].fs<p.fs) p.fs++;
		if(base[0].sc<p.sc) p.sc++;
		int id = (i==0?0:i+2);
		res[id] = p;
	}
	res[1] = P(res[0].fs,res[0].sc+1);
	res[2] = P(res[1].fs-1,res[1].sc);
	assert(res[2].fs==res[3].fs);
	// puts("--------");
	// show(res);
	// puts("--------");
	rotate(res.begin(),res.begin()+(N-s+1)%N,res.end());
	if(res[0].fs!=res[1].fs){
		rep(i,N) swap(res[i].fs,res[i].sc),res[i].fs*=-1;
	}
	assert(res[0].fs==res[1].fs);
	if(res[0].sc>res[1].sc){
		rep(i,N) res[i].fs*=-1, res[i].sc*=-1;
	}
	// show(as);
	// printf("erase %d,%d\n",s,(s+1)%N);
	// show(res);
	return res;
}
int main(){
	int N;
	vector<int> xs;
	cin>>N;
	int sum = 0;
	rep(i,N){
		int x;
		cin>>x;
		xs.pb(x);
		if(x==90) sum++;
		else sum--;
	}
	if(sum!=4){
		puts("-1");
		return 0;
	}
	vector<P> ans = construct(xs);
	rep(i,N) ans[i].fs += 5e8, ans[i].sc += 5e8;
	rep(i,N){
		cout<<ans[i].fs<<" "<<ans[i].sc<<endl;
	}
}

Submission Info

Judge Result