24h購物| | PChome| 登入
2012-12-01 21:38:05| 人氣1,766| 回應0 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

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

台長: Morris
人氣(1,766) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][cutpoint][關節點][dfs] 10199 - Tourist Guide
此分類上一篇:[UVA][模擬] 10686 - SQF Problems

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文