#include #include #include #include #include #include using namespace std; struct point { double x, y; bool highflag;}; struct line { struct point p1, p2; bool highflag;}; int ccw(struct point p0, struct point p1, struct point p2 ){ double dx1, dx2, dy1, dy2; dx1 = p1.x - p0.x; dy1 = p1.y - p0.y; dx2 = p2.x - p0.x; dy2 = p2.y - p0.y; if (dx1 * dy2 > dy1 * dx2) return +1; if (dx1 * dy2 < dy1 * dx2) return -1; if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return -1; if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return +1; return 0; } int intersect(struct line l1, struct line l2){ return ((ccw(l1.p1, l1.p2, l2.p1) *ccw(l1.p1, l1.p2, l2.p2)) <= 0) && ((ccw(l2.p1, l2.p2, l1.p1) *ccw(l2.p1, l2.p2, l1.p2)) <= 0); } struct point cross_point(struct line l1, struct line l2){ if (l1.p1.x == l1.p2.x){ if (l2.p1.y == l2.p2.y){ struct point temp; temp.x = l1.p1.x; temp.y = l2.p1.y; return temp; }else{ double p = (l2.p1.y - l2.p2.y) / (l2.p1.x - l2.p2.x); double q = -p * l2.p1.x + l2.p1.y; double y = p * l1.p1.x + q; struct point temp; temp.x = l1.p1.x; temp.y = y; return temp; } }else{ if (l2.p1.x == l2.p2.x){ if (l1.p1.y == l1.p2.y){ struct point temp; temp.x = l2.p1.x; temp.y = l1.p1.y; return temp; }else{ double p = (l1.p1.y - l1.p2.y) / (l1.p1.x - l1.p2.x); double q = -p * l1.p1.x + l1.p1.y; double y = p * l2.p1.x + q; struct point temp; temp.x = l2.p1.x; temp.y = y; return temp; } }else{ double p1 = (l1.p1.y - l1.p2.y) / (l1.p1.x - l1.p2.x); double q1 = -p1 * l1.p1.x + l1.p1.y; double p2 = (l2.p1.y - l2.p2.y) / (l2.p1.x - l2.p2.x); double q2 = -p2 * l2.p1.x + l2.p1.y; struct point temp; temp.x = -(q1 - q2) / (p1 -p2); temp.y = temp.x * p1 + q1; return temp; } } } struct MyGreater1 : public binary_function{ bool operator()(const struct point &p1, const struct point &p2){ return (p1.x > p2.x); } }; struct MyGreater2 : public binary_function{ bool operator()(const struct point &p1, const struct point &p2){ return (p1.y > p2.y); } }; int main(void) { int c; cin >> c; for (int i = 0; i < c; i++){ struct line newline; cin >> newline.p1.x >> newline.p1.y >> newline.p2.x >> newline.p2.y; int n; cin >> n; vector oldlines; for (int j = 0; j < n; j++){ struct line templine; cin >> templine.p1.x >> templine.p1.y >> templine.p2.x >> templine.p2.y; int o, l; cin >> o >> l; if (((o == 1) && (l == 1)) || (o == 0) && ( l == 0)) templine.highflag = true; else templine.highflag = false; oldlines.push_back(templine); } vector cross(n); for (int j = 0; j < n; j++){ if (intersect(newline, oldlines[j])) cross[j] = true; else cross[j] = false; } vector cross_points; for (int j = 0; j < n; j++){ if (cross[j]){ struct point temp; temp = cross_point(newline, oldlines[j]); temp.highflag = oldlines[j].highflag; cross_points.push_back(temp); } } stable_sort(cross_points.begin(), cross_points.end(), MyGreater1()); stable_sort(cross_points.begin(), cross_points.end(), MyGreater2()); // for (int j = 0; j < cross_points.size(); j++){ // cerr << cross_points[j].x << ' ' << cross_points[j].y << ' ' << cross_points[j].highflag <