読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 350 Railroad Conflict

ICPC 幾何 直線の交点

メモ:直線の交点のパラメータの求め方について。

問題

黒い線分と赤い線分が合わせて n 本フィールドに散らばっている。フィールドには地上・地下の2つのレイヤーがあり、どの線分も地上または地下にある。今から青い線分を与えられた点A, B間に1本引く。青い線分は、もし交わるならば黒い線文とは同じレイヤーで、赤い線分とは異なるレイヤーで交わるようにしたい。青い線分が地上と地下を行き来しなければならない最小の回数を求めよ。

制約

(気にしなくていい)

解法

青い線分と黒い/赤い線分の交点を、青い線分の片方の端点からもう一方の端点に向けてソートする必要がある。これは交点をベクトル表示したときのパラメータ t の大小によって可能である。 t は線分の交点を求める関数(crosspointSS)の内部で求まっているのでこれを使う。ただしcrosspointSSは線分が交差していることを前提にしていることに注意(intersectSSで先に判定が必要)。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
 
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
 
typedef complex<double> P;
const double EPS = 1e-10;
const double INF = 1e12;
 
struct L {
    P a, b, v;
    L(){}
    L(P _a, P _b) : a(_a), b(_b), v(b - a) {}
    L(double _ax, double _ay, double _bx, double _by) : L(P(_ax, _ay), P(_bx, _by)) {}
};
 
double cross(P a, P b) {
    return imag(conj(a) * b);
}
 
double dot(P a, P b) {
    return real(conj(a) * b);
}
 
int ccw(P p0, P p1, P p2) {
    if (cross(p1 - p0, p2 - p0) > 0) return +1; // counter-clockwise
    if (cross(p1 - p0, p2 - p0) < 0) return -1; // clockwise
    if (dot(p1 - p0, p2 - p0) < 0) return +2;   // online_back
    if (dot(p0 - p1, p2 - p1) < 0) return -2;   // online_front
    return 0;                                   // on_segment
}
 
bool intersectSS(L l1, L l2) {
    return (ccw(l1.a, l1.b, l2.a) * ccw(l1.a, l1.b, l2.b) <= 0 &&
            ccw(l2.a, l2.b, l1.a) * ccw(l2.a, l2.b, l1.b) <= 0);
}
 
double crosspointSS(L l1, L l2) {
    double d1 = abs(cross(l2.v, l1.a - l2.a));
    double d2 = abs(cross(l2.v, l1.b - l2.a));
    double t = d1 / (d1 + d2);
    // return l1.a + t * l1.v;
    return t;
}
 
L readL() {
    double xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    return L(xa, ya, xb, yb);
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int T;
    cin >> T;
    rep(_, T) {
        L blue = readL();
        int n;
        cin >> n;
        vector<L> lines(n);
        V layer(n);
        rep(i, n) {
            lines[i] = readL();
            int o, l;
            cin >> o >> l;
            layer[i] = l;
            if (o == 0) layer[i] ^= 1;
        }
 
        vector<pair<double, int>> v; // {t, id} 
        rep(i, n) {
            if (!intersectSS(blue, lines[i])) continue;
            v.emplace_back(make_pair(crosspointSS(blue, lines[i]), i));
        }
        sort(all(v));
 
        int ans = 0;
        rep(i, (int)v.size() - 1) {
            if (layer[v[i].second] != layer[v[i + 1].second]) {
                ans++;
            }
        }
 
        cout << ans << endl;
 
    }
}