2012-12-01 21:38:05Morris

[UVA][幾何][線段] 866 - Intersecting Line Segments

Intersecting line segments

Background

   In a 2-D Cartesian space, a straight line segment A is defined by two points A0=(x0,y0), A1=(x1,y1). 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

Problem

   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).

Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

   The first line of the input contains the integer number N of line segments. Each of the following N lines contains four integer values x0 y0 x1 y1,separated by a single space, that define a line segment.

Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

   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;
}