なんだこりゃ…。
http://community.topcoder.com/stat?c=problem_statement&pm=15098
問題
格子点で構成される多角形が与えられる。
この図形がシンプルであるか判定せよ。
解法
以下愚直に判定しよう。
- 隣接する辺が平行ではない
- 隣接しない辺が交点を持たない
条件に「辺の長さが正」というのがあるが、平行の判定方法に2ベクトルの張る面積を用いればそこで合わせて判定できる。
凸図形とは限らないため、隣接しない辺が一直線上に並ぶ場合があるので、注意すること。
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); } }
まとめ
最初解いたときは「2つの辺が一直線に並ぶ」ケースで見事落とした。