TopCoder SRM 599 Div1 Medium FindPolygons

コーナーケースを見落としたもったいない問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12842

問題

以下の多角形をsimple polygonと呼ぶことにする。

• 各頂点は格子点上にある
• 複数の頂点は同じ作業に
• 辺の長さの総和は整数Lである

Lが与えられたとき、simple polygonが作れるか。
また作れる場合は：

• 辺の数が最少
• 同じ辺の数の場合は、最短辺と最長辺の長さの差が最小

のものを求め、最短辺と最長辺の長さの差を答えよ。

解法

この問題は5角形以上は解になりえない(本番後にわかった)。

• Lが偶数の場合、4角形が確実に作れるので5角形以上を考える必要がない。
• Lが奇数の場合、そもそも題意を満たすsimple polygonは作れない

後者を証明しておく。
Lが整数なので、各頂点を結んだ辺の長さも整数でなければならない。
この時、2点のX座標の差とY座標の差の偶奇と辺の長さの偶奇を考えると、(偶・偶・偶)(奇・偶・奇)(遇・奇・奇)の3通りしかない。
すなわち、X座標の偶奇とY座標の偶奇のxorが辺の長さのxorとなる。
多角形上ある点から各辺を1周まわって戻ってくると、移動したX方向の長さの和とY方向の長さの和はともに偶数なので、Lは偶数でなければならない。

Lが偶数とすると、4角形は正方形に近いものを作ればいいので簡単。
後は3角形を作ればよい。
原点から距離Pの格子点と距離Qの格子点からなる3角形があるとすると、2つの格子点の間の長さがL-P-Qになるように出来ればsimple polygonとなる。
よって事前に距離が整数となる格子点を列挙しておいて全探索すればよい。
原点とPとQが一直線に並ぶ場合だけ注意。

なお、L=2はsimple polygonが作れないので注意。自分はこれで落とした…。

vector<pair<int,int> > A[2502];
int mat[2501][2501];

class FindPolygons {
	public:
	
	void setup(int L) {
		int i,x,y;
		
		for(x=1;x<=1+L/2;x++) A[x].clear();
		for(x=1;x<=1+L/2;x++) {
			for(y=1;y<=1+L/2;y++) {
				double z = sqrt(x*x+y*y+1e-9);
				if(z>L/2+1) break;
				if(x*x+y*y == (int)z*(int)z) {
					A[(int)z].push_back(make_pair(x,y));
					mat[x][y]=(int)z;
				}
			}
		}
		for(x=1;x<=1+L/2;x++) {
			A[x].push_back(make_pair(0,x));
			A[x].push_back(make_pair(x,0));
			mat[0][x]=x;
			mat[x][0]=x;
		}
	}
	
	int okok(int x,int y,int z) {
		return x*x+y*y==z*z;
	}
	
	int check3(int L) {
		int re=9999999;
		int x,y,z,ma,x2,y2;
		for(x=1;x<=L/2;x++) {
			for(y=x;y<=L/2;y++) {
				z=L-x-y;
				if(z>=x+y || z<=0) continue;
				ma=max(max(abs(x-y),abs(y-z)),abs(z-x));
				if(ma>=re) continue;
				FOR(x2,A[x].size()) FOR(y2,A[y].size()) {
					int ax=A[x][x2].first;
					int ay=A[x][x2].second;
					int bx=A[y][y2].first;
					int by=A[y][y2].second;
					if(ax*by==ay*bx) {
						if((okok(ax-bx,ay+by,z) && ay+by!=0) ||
						   (okok(ax+bx,ay-by,z) && ax+bx!=0)) {
							re=ma;
							goto ne;
						}
					}
					else {
						if(okok(ax+bx,ay+by,z) || okok(ax+bx,ay-by,z) || okok(ax-bx,ay+by,z) || okok(ax-bx,ay-by,z)) {
							re=ma;
							goto ne;
						}
					}
				}
			}
			ne:
			;
		}
		return re;
	}
	
	double minimumPolygon(int L) {
		int re;
		if(L<=3) return -1;
		
		setup(L);
		
		re=check3(L);
		if(re<L) return re;
		if(L%2==0) return L%4!=0;
		return -1;
		
	}
};

まとめ

L==2ではまった人は他にもちらほらいたようだ。
せっかく一直線ケースは本番に気づいたのになぁ。

5角形以上はない、ってのは本番には証明できなかった。