Submission #1001081

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define p pair<int,int>
#define x first
#define y second
// num, 
p rot(p pt){
	p d;
	d.x = pt.y;
	d.y = -pt.x;
	return d;
}
vector<p> solve(vector<int> d){

	if(d.size() == 4){
		vector<p> ans;
		ans.push_back(p(0, 0));
		ans.push_back(p(1, 0));
		ans.push_back(p(1, 1));
		ans.push_back(p(0, 1));
		return ans;
	}

	vector<int> newd;
	int n = d.size();
	int sh = 0;
	for(int i = 0; i < d.size(); i++){
		if(d[i%n] == 90 && d[(i+1)%n] == 90 && d[(i+2)%n] == 270) sh = i;
	}
	for(int i = 0; i < d.size(); i++){
		newd.push_back(d[(i+sh)%n]);
	}

	//newd is d (question) wrapped around

	vector<int> dsmall;
	for(int i = 0; i < d.size(); i++){
		if(i != 1 && i != 2) dsmall.push_back(newd[i]);
	}

	vector<p> asmall = solve(dsmall); //solution to wrapped around

	/*for(int i = 0; i < dsmall.size(); i++){
		cout << dsmall[i] << " ";
	}
	cout << endl;

	for(int i = 0; i < dsmall.size(); i++){
		cout << asmall[i].x << "," << asmall[i].y << " ";
	}
	cout << endl;*/

	int nrot = 0;
	while((asmall[asmall.size()-1].y != asmall[0].y) || (asmall[asmall.size()-1].x > asmall[0].x)){
		nrot++;
		for(int i = 0; i < asmall.size(); i++){
			asmall[i] = rot(asmall[i]);
		}
	}

	/*cout << nrot << endl;
	for(int i = 0; i < dsmall.size(); i++){
		cout << asmall[i].x << "," << asmall[i].y << " ";
	}
	cout << endl;*/

	// asmall has horizontal right segment
	int sx = asmall[0].x;
	int sy = asmall[0].y;
	for(int i = 0; i < asmall.size(); i++){
		if(asmall[i].x > sx) asmall[i].x+=2;
		if(asmall[i].x < sx) asmall[i].x-=2;
		if(asmall[i].y > sy) asmall[i].y+=2;
		if(asmall[i].y < sy) asmall[i].y-=2;
	}
	vector<p> ans;
	ans.push_back(p(asmall[0].x+1,asmall[0].y));
	ans.push_back(p(asmall[0].x+1,asmall[0].y+1));
	ans.push_back(p(asmall[0].x,asmall[0].y+1));
	for(int i = 1; i < asmall.size(); i++){
		ans.push_back(asmall[i]);
	}
	for(int cc = 0; cc < 4-nrot; cc++){
		for(int i = 0; i < ans.size(); i++){
			ans[i] = rot(ans[i]);
		}
	}

	vector<p> finans;
	for(int i = 0; i < ans.size(); i++){
		finans.push_back(ans[(n-sh+i)%n]);
	}
	/*for(int i = 0; i < d.size(); i++){
		cout << d[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < ans.size(); i++){
		cout << finans[i].x << "," << finans[i].y << " ";
	}
	cout << endl << endl;*/
	return finans;

}
int main(){
	int n;
	cin >> n;
	int a[n];
	int d = 0;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		if(a[i] == 90) d++;
		if(a[i] == 270) d--;
	}
	int flip = 0;
	if(d == -4){
		flip = 1;
		d = -d;
	}
	if(d != 4){
		cout << -1 << endl;
		return 0;
	}
	vector<int> pr;
	for(int i = 0; i < n; i++) pr.push_back(a[i]);
	vector<p> ttt = solve(pr);
	for(int i = 0; i < ttt.size(); i++){
		cout << ttt[i].x+10000000 << " " << ttt[i].y+10000000 << endl;
	}
}

Submission Info

Judge Result