/* 2006 ACM ICPC 国内予選模擬練習会 D 問題ソース 入力 xa ya xb yb n xs1 ys1 xt1 yt1 o1 xs2 ys2 xt2 yt2 o2 ... xsn ysn xtn ytn on 各座標 x + i y を {(x - xa) + i (y - ya)} / {(xb - xa) + i (yb - ya)} と変換する これをすると xa + i ya は 0 に,(xb + i yb) は 1 へと変換される 変換後の xs + i ys から xt + i yt の成す線分が 0 から 1 の成す線分と交わる点を求める (xs, ys) と (xt, yt) を通る直線の方程式は (y - ys) * (xt - xs) - (yt - ys) * (x - xs) = 0 これに y = 0 を代入 x = (xs*yt - xt*ys) / (yt - xs); ただし、これは直線同士の交点なので、これが線分同士の交点になるかをチェックする 直線 x軸と線分 (xs, ys) (xt, yt) が交わる <=> ys と yt が異符号 <=> ys * yt < 0.0 線分 (0, 0) (1, 0) と直線 (xs, ys) (xt, yt) が交わる <=> 0.0 < x < 1.0 あとは vector > に交点の x 座標と 高架にするべきかどうかを入れて sort 第二要素の bool の値が変わっている回数を数えて出力 */ #include #include #include using namespace std; typedef complex cd; int main(void){ int q; for(cin >> q; q>0; q--){ double xa, ya, xb, yb; cin >> xa >> ya >> xb >> yb; cd p = cd(xa, ya); cd v = cd(xb, yb) - p; vector > vec; int n; for(cin >> n; n>0; n--){ double xs, ys, xt, yt, x; int o, l; cin >> xs >> ys >> xt >> yt >> o >> l; cd s = (cd(xs, ys) - p) / v; cd t = (cd(xt, yt) - p) / v; xs = real(s); ys = imag(s); xt = real(t); yt = imag(t); x = (xs*yt - xt*ys) / (yt - xs); if(ys * yt < 0.0 && 0.0