Maximum-Cup 2013 : C - 白蛇のお守り

ここら辺はまだ簡単。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_c

問題

2つの点が与えられ、その間に線分を引く。
その他にいくつか線分が与えられるので、最初の線分と交差する数を答えよ。

解法

線分の交差判定なので、外積を使って片方の線分の両端がもう片方の線分の左右両側にあることを確認すればよい。
注意点として、2つの線分を伸ばした直線が重なる場合、別途線分が重なってるか判定が必要となる。

int N,NX,NY,QX,QY;

void solve() {
	int f,i,j,k,l,x,y;
	
	k=1;
	cin>>N>>NX>>NY>>QX>>QY;
	QX-=NX;
	QY-=NY;
	
	FOR(i,N-1) {
		int AX,AY,BX,BY;
		cin>>AX>>AY>>BX>>BY;
		AX-=NX;
		AY-=NY;
		BX-=NX;
		BY-=NY;
		
		if((AX*QY-AY*QX)==0 && (BX*QY-BY*QX)==0) {
			//par
			if(QX==0 && (min(AY,BY)>max(0,QY) || max(AY,BY)<min(0,QY))) continue;
			if(QX!=0 && (min(AX,BX)>max(0,QX) || max(AX,BX)<min(0,QX))) continue;
		}
		else {
			if((AX*QY-AY*QX)*(ll)(BX*QY-BY*QX)>0) continue;
			if((ll)((QX-AX)*(BY-AY)-(QY-AY)*(BX-AX))*((0-AX)*(BY-AY)-(0-AY)*(BX-AX))>0) continue;
		}
		k++;
	}
	_P("%d\n",k);
}

まとめ

まだ解き終わってないDを見てても思うけど、やっぱり幾何ライブラリ作った方がいいかな…。