めんどくさそうで放置したけど、ようやく頑張った。
http://codeforces.com/contest/598/problem/F
問題
2次元座標上でsimpleな多角形が与えられる(凹な可能性はある)。
ここにM個の直線が与えられる。
それぞれ、直線と多角形の共通部分の長さを求めよ。
解法
他人の解法を参考に解いた。
直線は線分の形で与えられるので、まずは両端が確実に多角形の外側に出るまで延長しよう。
この直線と、多角形の辺が交わる(点で接するも含む)かどうかを符号付き面積で求めよう。
交わる場合、直線と辺はその交点において、多角形の中から外にでるか、外から中に入るのどちらかである。
仮に多角形の頂点が反時計まわりに配置されているとすると、直線の始点が辺の左側、終点が右側なら多角形の中から外へでる、逆なら外から中へ入ると考えられる。
多角形の中にいる状態を+2、外にいる状態を0とする。
多角形と辺の交点を始点から順にソートしよう。
直線が辺と交差し、中に入るなら状態が+2、外に出るなら-2変化すると考える。
交差しきらず辺上で止まるなら状態変化は+1/-1にとどまり、辺と直線が乗るなら±0と考える。
交点を順に見て状態の累積和を取り、状態が正の間の長さを取れば解となる。
(上記は多角形の頂点が反時計回りの場合である。入力は時計回りの可能性があるので、その場合状態が負の区間の長さを取ればよい。いずれも、0かどうかを判定すればすむ。)
typedef complex<double> Po; struct Line { Po a,b; Line(const Po &a,const Po &b) : a(a),b(b){Rep();}; void Rep(){ if(a.real()==b.real()) { a=Po(a.real(),0); b=Po(b.real(),1); return; } // Y-axis Po c,d; d=Po(1,(b.imag()-a.imag())/(b.real()-a.real())); c=Po(0,b.imag()-b.real()*d.imag()); d=Po(1,d.imag()+c.imag()); a=c; b=d; }; }; Po CrossPoint(const Line &l,const Line &r) { Po p,ld=l.b-l.a,rd=r.b-r.a,d3=l.b-r.a; double aa=ld.real()*rd.imag()-ld.imag()*rd.real(); double bb=ld.real()*d3.imag()-ld.imag()*d3.real(); if(abs(aa)<1e-9 && abs(bb)<1e-9) return Po(1e9,-1e9); //same if(abs(aa)<1e-9) return Po(1e9,1e9); //parallel return r.a+bb/aa*(r.b-r.a); }; int N,M; int X[1010],Y[1010]; ll comb(double a) { if(a==0) return 0; if(a>0) return a*100+0.1; if(a<0) return -(-a*100+0.1); } double hoge(ll sx,ll sy,ll dx,ll dy) { if(dx<0 || (dx==0 && dy<0)) sx+=dx, sy+=dy, dx=-dx, dy=-dy; pair<double,double> st={sx,sy}; pair<double,double> ed={sx+dx,sy+dy}; ll L=max(abs(dx),abs(dy)); ll mul=100000000/L+2; pair<double,double> lst={sx-dx*mul,sy-dy*mul}; pair<double,double> rst={sx+dx*mul,sy+dy*mul}; vector<pair<pair<double,double>,int> > V; int i; FOR(i,N) { pair<double,double> a={X[i],Y[i]},b={X[i+1],Y[i+1]}; ll dx2=X[i+1]-X[i],dy2=Y[i+1]-Y[i]; ll ad=(X[i]-lst.first)*(rst.second-lst.second)-(Y[i]-lst.second)*(rst.first-lst.first); ll bd=(X[i+1]-lst.first)*(rst.second-lst.second)-(Y[i+1]-lst.second)*(rst.first-lst.first); if(dy*dx2==dx*dy2) { if(ad==0 && bd==0) { auto lef=max(st,min(a,b)); auto ri=min(ed,max(a,b)); V.push_back({lef,0}); V.push_back({ri,0}); } } else { if(ad>0&&bd>0) continue; else if(ad<0&&bd<0) continue; else if(ad==0) V.push_back({{X[i],Y[i]},(bd>0)?1:-1}); else if(bd==0) V.push_back({{X[i+1],Y[i+1]},(ad>0)?-1:1}); else { Po p1(lst.first,lst.second); Po p2(rst.first,rst.second); Po p3(X[i],Y[i]); Po p4(X[i+1],Y[i+1]); Line L1(p1,p2),L2(p3,p4); Po c=CrossPoint(L1,L2); V.push_back({{c.real(),c.imag()},(ad>0)?-2:2}); } assert(ad||bd); } } sort(ALL(V)); pair<double,double> pre=lst; int status=0; double len=0; FORR(r,V) { if(status) len += hypot(pre.first-r.first.first,pre.second-r.first.second); status+=r.second; pre=r.first; } return len; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { double dx,dy; cin>>dx>>dy; X[i]=comb(dx); Y[i]=comb(dy); } X[N]=X[0]; Y[N]=Y[0]; FOR(r,M) { double tx1,ty1,tx2,ty2; cin>>tx1>>ty1>>tx2>>ty2; _P("%.12lf\n",hoge(comb(tx1),comb(ty1),comb(tx2)-comb(tx1),comb(ty2)-comb(ty1))/100.0); } }
まとめ
辺と直線が乗ることを考えるとホント面倒な問題。
EducationalなRoundなのでそう文句もないけど。