Segment Segment Intersection

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

bool isEq(double a, double b)
{
    return (abs(a - b) < 1e-9);
}

struct point {
    double x, y;
    bool operator==(const point& p)const
    {
        return (isEq(x, p.x) && isEq(y, p.y));
    }
};

struct segment {
    point st, en;
    segment() { st = {0, 0}; en = {0, 0}; }
    segment(point A, point B) { st = A; en = B; }
    bool operator==(const segment& AB)const
    {
        return ((st == AB.st && en == AB.en) || (st == AB.en && en == AB.st));
    }
};

double det(point& a, point& b, point& c)
{
    return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}

bool isIntersect(segment& AB, segment& CD, point& p)
{
    double ABC = det(AB.st, AB.en, CD.st);
    double ABD = det(AB.st, AB.en, CD.en);
    double CDA = det(CD.st, CD.en, AB.st);
    double CDB = det(CD.st, CD.en, AB.en);

    if (((ABC > 0 && ABD < 0) || (ABC < 0 && ABD > 0)) && ((CDA > 0 && CDB < 0) || (CDA < 0 && CDB > 0))) {
        if (isEq(AB.st.x, AB.en.x)) {
            p.x = AB.st.x;
            p.y = ((CD.st.y - CD.en.y) / (CD.st.x - CD.en.x))*(p.x - CD.st.x) + CD.st.y;
            return 1;
        }
        if (isEq(CD.st.x, CD.en.x)) {
            p.x = CD.st.x;
            p.y = ((AB.st.y - AB.en.y) / (AB.st.x - AB.en.x))*(p.x - AB.st.x) + AB.st.y;
            return 1;
        }

        double a1, b1, c1, a2, b2, c2;
        a1 = AB.st.y - AB.en.y;
        b1 = AB.en.x - AB.st.x;
        c1 = (AB.st.y*b1 + AB.st.x*a1);

        a2 = CD.st.y - CD.en.y;
        b2 = CD.en.x - CD.st.x;
        c2 = (CD.st.y*b2 + CD.st.x*a2);

        p.x = (b2*c1 - b1*c2) / (b2*a1 - b1*a2);
        p.y = (c1 - a1*p.x) / b1;
        return 1;
    }
    else if (isEq(ABC, 0)) {
        if ((max(AB.st.x, AB.en.x) > CD.st.x && min(AB.st.x, AB.en.x) < CD.st.x) && (max(AB.st.y, AB.en.y) > CD.st.y && min(AB.st.y, AB.en.y) < CD.st.y)) {
            p = CD.st;
            return 1;
        }
    }
    else if (isEq(ABD, 0)) {
        if ((max(AB.st.x, AB.en.x) > CD.en.x && min(AB.st.x, AB.en.x) < CD.en.x) && (max(AB.st.y, AB.en.y) > CD.en.y && min(AB.st.y, AB.en.y) < CD.en.y)) {
            p = CD.en;
            return 1;
        }
    }

    else if (isEq(CDA, 0)) {
        if ((max(CD.st.x, CD.en.x) > AB.st.x && min(CD.st.x, CD.en.x) < AB.st.x) && (max(CD.st.y, CD.en.y) > AB.st.y && min(CD.st.y, CD.en.y) < AB.st.y)) {
            p = AB.st;
            return 1;
        }
    }
    else if (isEq(CDB, 0)) {
        if ((max(CD.st.x, CD.en.x) > AB.en.x && min(CD.st.x, CD.en.x) < AB.en.x) && (max(CD.st.y, CD.en.y) > AB.en.y && min(CD.st.y, CD.en.y) < AB.en.y)) {
            p = CD.en;
            return 1;
        }
    }
    else return 0;
}

int main()
{
    //freopen("out.txt", "w", stdout);
    int i, j, k, l, t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        vector<segment>lines;
        segment AB;
        for (i = 0; i < n; i++) {
            scanf("%lf %lf %lf %lf", &AB.st.x, &AB.st.y, &AB.en.x, &AB.en.y);
            lines.push_back(AB);
        }

        vector<segment>lines2, lines3;
        //cout << lines[1] == lines[1] << endl;
        bool f = false;
        point p;
        do {
            int s = lines.size();
            f = false;
            for (i = 0; i < s; i++) {
                for (j = i + 1; j < s; j++) {
                    if (isIntersect(lines[i], lines[j], p)){
                        f = true;
                        cout << lines[i].st.x << ','<< lines[i].st.y << "  " << lines[i].en.x << ',' << lines[i].en.y << '\t' << lines[j].st.x << ',' << lines[j].st.y << "  " << lines[j].en.x << ',' << lines[j].en.y << '\t' << p.x << ',' << p.y << endl;
                        lines2.push_back(segment(p, lines[i].st));
                        lines2.push_back(segment(p, lines[i].en));
                        lines2.push_back(segment(p, lines[j].st));
                        lines2.push_back(segment(p, lines[j].en));

                        lines3.push_back(lines[i]);
                        lines3.push_back(lines[j]);
                    }
                }
            }

            vector<segment>::iterator it;
            for (i = 0; i < lines3.size(); i++) {
                it = find(lines.begin(), lines.end(), lines3[i]);
                if(it != lines.end())lines.erase(it);
            }
            lines.reserve(lines.size() + lines2.size());
            lines.insert(lines.end(), lines2.begin(), lines2.end());

            lines2.clear();
            lines3.clear();
        } while (f);

        lines2.clear();
        for (i = 0; i < lines.size(); i++) {
            if (count(lines2.begin(), lines2.end(), lines[i]) == 0) {
                lines2.push_back(lines[i]);
                cout << lines[i].st.x << ' ' << lines[i].st.y << '\t' << lines[i].en.x << ' ' << lines[i].en.y << endl;
            }
        }
        printf("%d\n", lines2.size());
    }
    return 0;
}