题解：【CODE FESTIVAL 2016 Grand Final】90 and 270

题目链接

经典增量构造题。

不妨从是否存在构造开始考虑：根据多边形内角和的公式容易得出给定的度数和必须等于 \((n-2) \times 180^{\circ}\)，才有解。

换一个角度思考，又因为只有 \(90^{\circ}\) 和 \(270^{\circ}\)，所以这两种角的数量都是一定的，即 \(90^{\circ}\) 永远比 \(270^{\circ}\) 多四个，这当然也可以成为是否有解的判断条件。

容易发现，如果有连续的 \(90^{\circ}\) 和 \(270^{\circ}\)，原来的线段走向将不变，那么我们就可以将其消去，从而将 \(n\) 转化为 \(n-2\) 的子问题。在这里我们也可以得到一个没啥用的性质，就是有解情况 \(n\) 必须为偶数。

不断消消消，我们最后会得到什么呢？不错，就是多出来的那四个 \(90^{\circ}\)。因此我们总是能够得到一个矩形，然后再进行逆操作，分四种情况讨论，还原出消掉的拐角，从而得到了递归解决问题的写法。

为什么总有 \(90^{\circ}\) 和 \(270^{\circ}\) 相邻呢？因为多边形实质是个环，\(270^{\circ}\) 旁边肯定有 \(90^{\circ}\)，不断递归就好了。

有了大致思路，如何在坐标上表达出来这个图形呢？将 \(n=4\) 作为边界，手动构造一个矩形。反正坐标系足够大，不妨每次跳出一层的时候直接将坐标扩大一倍，在加加减减的还原微调之后再离散化就好了。

时间复杂度 \(O(n^2 \log n)\)，瓶颈在于离散化，实际上链表直接插可能更优吧。

\(Code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}

namespace LgxTpre
{
	static const int MAX=100010;
	static const int mod=998244353;
	static const int INF=200707070707;
	
	int n;
	int sum;
	vector<int> t;
	
	struct point
	{
		int x,y;
		point(int _x,int _y)
		{
			x=_x,y=_y;
			return;
		}
	};
	
	int dx[MAX],dy[MAX];
	int cntx,cnty;
	
	vector<point> solve(vector<int> s)
	{
		int m=s.size();
		if(m==4) return {point(0,0),point(1,0),point(1,1),point(0,1)};
		int pos=0;
		while(s[pos]!=90||s[(pos+1)%m]!=270) ++pos;
		vector<int> tt;
		pos=(pos-1+m)%m;
		for(int i=0;i<m;++i)
			if(i!=1&&i!=2)
				tt.push_back(s[(pos+i)%m]);
		vector<point> p=solve(tt);
		
		for(auto &it:p)
			it.x<<=1,it.y<<=1;
		if(p[0].x==p[1].x)
		{
			if(p[0].y<p[1].y)
				--p[1].x,
				p.insert(p.begin()+1,{point(p[0].x,p[0].y+1),point(p[0].x-1,p[0].y+1)});
			else
				++p[1].x,
				p.insert(p.begin()+1,{point(p[0].x,p[0].y-1),point(p[0].x+1,p[0].y-1)});
		}
		else
		{
			if(p[0].x<p[1].x)
				++p[1].y,
				p.insert(p.begin()+1,{point(p[0].x+1,p[0].y),point(p[0].x+1,p[0].y+1)});
			else
				--p[1].y,
				p.insert(p.begin()+1,{point(p[0].x-1,p[0].y),point(p[0].x-1,p[0].y-1)});
		}
		rotate(p.begin(),p.begin()+m-pos,p.end());
		
		for(auto it:p)
			dx[++cntx]=it.x,dy[++cnty]=it.y;
		sort(dx+1,dx+cntx+1),sort(dy+1,dy+cnty+1);
		cntx=unique(dx+1,dx+cntx+1)-dx-1,cnty=unique(dy+1,dy+cnty+1)-dy-1;
		for(auto &it:p)
			it.x=lower_bound(dx+1,dx+cntx+1,it.x)-dx-1,
			it.y=lower_bound(dy+1,dy+cnty+1,it.y)-dy-1;
		memset(dx,0,sizeof dx); cntx=0;
		memset(dy,0,sizeof dy); cnty=0;
		return p;
	}
	
	inline void lmy_forever()
	{
		n=read();
		for(int i=1;i<=n;++i)
			t.push_back(read()),sum+=t.back();
		if(sum!=(n-2)*180) {cout<<-1; return;}
		vector<point> ans=solve(t);
		for(auto it:ans)
			cout<<it.x<<" "<<it.y<<endl;
		return;
	}
}

signed main()
{
	LgxTpre::lmy_forever();
	return (0-0);
}