$\epsilon = 10^{-10}$としたらWAった。$10^{-6}$にしたら通った。

solution

線分の交差判定をするだけ。$O(N)$。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

const double eps = 1e-6;
typedef complex<double> point;
struct circle { point c; double r; };
struct line { point s, t; };
struct segment { point s, t; };
struct ray { point s, t; };
double   dot(point p, point q) { return real(p * conj(q)); }
double cross(point p, point q) { return imag(conj(p) * q); }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
bool does_intersect(point a, line b) {
    return ccw(0, a - b.s, b.t - b.s) == 0;
}
bool does_intersect(line a, point b) {
    return does_intersect(b, a);
}
bool is_parallel(line a, line b) {
    return ccw(0, a.t - a.s, b.t - b.s) == 0;
}
bool is_overwraped(line a, line b) {
    return does_intersect(a.s, b)
        and does_intersect(a.t, b);
}
bool does_intersect(line a, line b) {
    return not is_parallel(a, b)
        and not is_overwraped(a, b);
}
point intersection(line a, line b) {
    assert (does_intersect(a, b));
    double p = cross(a.t - a.s, b.t - b.s);
    double q = cross(a.t - a.s, a.t - b.s);
    return (q / p) * (b.t - b.s) + b.s;
}
bool does_intersect(point a, segment b) {
    return abs(cross(b.t - b.s, a - b.s)) < eps
        and dot(b.t - b.s, a - b.s) > - eps
        and dot(b.s - b.t, a - b.t) > - eps;
}
bool does_intersect(segment a, point b) {
    return does_intersect(b, a);
}
template <typename T, typename U>
bool does_intersect_linelikes(T const & a, U const & b) {
    if (not does_intersect(to_line(a), to_line(b))) return false;
    point c = intersection(to_line(a), to_line(b));
    return does_intersect(a, c)
        and does_intersect(b, c);
}
line to_line(segment a) {
    return { a.s, a.t };
}
bool does_intersect(segment a, segment b) {
    return does_intersect_linelikes(a, b);
}
point intersection(segment a, segment b) {
    assert (does_intersect(a, b));
    return intersection(to_line(a), to_line(b));
}

int main() {
    int testcase; scanf("%d", &testcase);
    while (testcase --) {
        segment a; { int ax, ay, bx, by; scanf("%d%d%d%d", &ax, &ay, &bx, &by); a = { point(ax, ay), point(bx, by) }; }
        int n; scanf("%d", &n);
        vector<pair<double, bool> > events;
        repeat (i, n) {
            segment b; { int ax, ay, bx, by; scanf("%d%d%d%d", &ax, &ay, &bx, &by); b = { point(ax, ay), point(bx, by) }; }
            int o, t; scanf("%d%d", &o, &t);
            if (does_intersect(a, b)) {
                point p = intersection(to_line(a), to_line(b));
                events.emplace_back(abs(p - a.s), o ^ t);
            }
        }
        whole(sort, events);
        int last = -1;
        int result = 0;
        for (auto event : events) {
            bool type = event.second;
            if (last != -1 and last != int(type)) {
                result += 1;
            }
            last = int(type);
        }
        printf("%d\n", result);
    }
    return 0;
}