Intersecting line segments

   In a 2-D Cartesian space, a straight line segment A is defined by two points A₀=(x₀,y₀), A₁=(x₁,y₁). The intersection of line segments A and B (if there is one), together with the initial four points, defines four new line segments.
   In Figure 1.1, the intersection P between lines B and C defines four new segments. As a result, the toal amount of line segments after the evaluation of intersections is five.

Figure 1.1 - Intersections of line segments

   Given an initial set of lines segments, determine the number of line segments resulting from the evaluation of all the possible intersections.
   It is assumed, as a simplification, that no coincidences may occur between coordinates of singular points (intersections or end points).

   The first line of the input contains the integer number N of line segments. Each of the following N lines contains four integer values x₀ y₀ x₁ y₁,separated by a single space, that define a line segment.

   The integer number of lines segments after all the possible intersections are evaluated.

Sample Input
1

5
3 1 3 8
4 1 4 8
2 4 9 4
8 7 5 7
5 6 10 1

Sample Output
11

當有交點的時候，線段就會斷開成為新的線段，求最後的線段總數。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define eps 1e-6
using namespace std;
struct Point {
    double x, y;
};
struct Segment {
    Point s, e;
};
int onSeg(Segment a, Point b) {
    return min(a.s.x, a.e.x) <= b.x && max(a.s.x, a.e.x) >= b.x &&
    min(a.s.y, a.e.y) <= b.y && max(a.s.y, a.e.y) >= b.y;
}
Point p;
int solve(Segment a, Segment b) {
    double a1, b1, c1, a2, b2, c2;
    double D, Dx, Dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    D = a1*b2-a2*b1;
    Dx = c1*b2 - c2*b1;
    Dy = a1*c2 - a2*c1;
    if(!D && (Dx || Dy)) // NONE
        return 0;
    else if(!D && !Dx && !Dy) // LINE
        return 0;
    else {
        p.x = Dx/D, p.y = Dy/D;
        if(fabs(p.x-a.s.x) < eps && fabs(p.y-a.s.y) < eps)
            return 0;
        if(fabs(p.x-a.e.x) < eps && fabs(p.y-a.e.y) < eps)
            return 0;
        if(fabs(p.x-b.s.x) < eps && fabs(p.y-b.s.y) < eps)
            return 0;
        if(fabs(p.x-b.e.x) < eps && fabs(p.y-b.e.y) < eps)
            return 0;
        if(onSeg(a, p) && onSeg(b, p))
            /*printf("POINT %.2lf %.2lf\n", p.x, p.y)*/;
        else
            return 0;
    }
    return 1;
}
int main() {
    int t, n, tn, i, j;
    scanf("%d", &t);
    while(t--) {
        Segment A[100];
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%lf %lf %lf %lf", &A[i].s.x, &A[i].s.y, &A[i].e.x, &A[i].e.y);
        do {
            tn = n;
            for(i = 0; i < n; i++) {
                for(j = i+1; j < n; j++) {
                    if(solve(A[i], A[j])) {
                        A[tn] = A[i];
                        A[i].e = p, A[tn].s = p, tn++;
                        A[tn] = A[j];
                        A[j].e = p, A[tn].s = p, tn++;
                    }
                }
            }
            if(tn != n) n = tn;
            else    break;
        } while(1);
        printf("%d\n", n);
        if(t)   puts("");
    }
    return 0;
}