Codeforces ECR #001 : F. Cut Length

めんどくさそうで放置したけど、ようやく頑張った。
http://codeforces.com/contest/598/problem/F

問題

２次元座標上で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なのでそう文句もないけど。