TopCoder SRM 739 Div2 Hard CheckPolygon

なんだこりゃ…。
http://community.topcoder.com/stat?c=problem_statement&pm=15098

問題

格子点で構成される多角形が与えられる。
この図形がシンプルであるか判定せよ。

解法

以下愚直に判定しよう。

• 隣接する辺が平行ではない
• 隣接しない辺が交点を持たない

条件に「辺の長さが正」というのがあるが、平行の判定方法に２ベクトルの張る面積を用いればそこで合わせて判定できる。
凸図形とは限らないため、隣接しない辺が一直線上に並ぶ場合があるので、注意すること。

class CheckPolygon {
	public:
	
	int ispar(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3) {
		x1-=x2;
		x3-=x2;
		y1-=y2;
		y3-=y2;
		return x1*y3-x3*y1==0;
		
	}
	int cross(ll x11,ll y11,ll x12,ll y12,ll x21,ll y21,ll x22,ll y22) {
		ll a=(x21-x11)*(y12-y11)-(y21-y11)*(x12-x11);
		ll b=(x22-x11)*(y12-y11)-(y22-y11)*(x12-x11);
		if(a && b && ((a<0)==(b<0))) return 0;
		a=(x11-x21)*(y22-y21)-(y11-y21)*(x22-x21);
		b=(x12-x21)*(y22-y21)-(y12-y21)*(x22-x21);
		
		if(a && b && ((a<0)==(b<0))) return 0;
		return 1;
	}
	int ison(ll x1,ll y1,ll x2,ll y2) {
		return (x1*x2+y1*y2<=0) && (x1*y2-x2*y1==0);
	}
	
	string check(vector <int> X, vector <int> Y) {
		int N=X.size();
		X.push_back(X[0]);
		Y.push_back(Y[0]);
		int i,j;
		FOR(i,N) if(X[i]==X[i+1] && Y[i]==Y[i+1]) return "Not simple";
		FOR(i,N-1) if(ispar(X[i],Y[i],X[i+1],Y[i+1],X[i+2],Y[i+2])) return "Not simple";
		
		FOR(i,N) FOR(j,N) if(abs(i-j)>1 && abs(i-j)<N-1) {
			
			if(ispar(X[i],Y[i],X[i+1],Y[i+1],X[j+1]-X[j]+X[i+1],Y[j+1]-Y[j]+Y[i+1])) {
				if(ison(X[i]-X[j],  Y[i]-Y[j],  X[i+1]-X[j],  Y[i+1]-Y[j])) return "Not simple";
				if(ison(X[i]-X[j+1],Y[i]-Y[j+1],X[i+1]-X[j+1],Y[i+1]-Y[j+1])) return "Not simple";
				if(ison(X[j]-X[i],  Y[j]-Y[i],  X[j+1]-X[i],  Y[j+1]-Y[i])) return "Not simple";
				if(ison(X[j]-X[i+1],Y[j]-Y[i+1],X[j+1]-X[i+1],Y[j+1]-Y[i+1])) return "Not simple";
			}
			else {
				if(cross(X[i],Y[i],X[i+1],Y[i+1],X[j],Y[j],X[j+1],Y[j+1])) return "Not simple";
			}
		}
		
		ll a=0;
		FOR(i,N) a+=1LL*X[i+1]*Y[i]-1LL*Y[i+1]*X[i];
		a=abs(a);
		
		char buf[50];
		sprintf(buf, "%lld.%d",a/2,(a%2)?5:0);
		return string(buf);
		
	}
}

まとめ

最初解いたときは「２つの辺が一直線に並ぶ」ケースで見事落とした。