解題區/解題區 - UVa

UVa 10709 - Intersection is Not that Easy

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

In this problem your job is to find the distance between two lines or a line and a line segment or two line segments. Suppose we have two points A(x1,y1) and B(x2,y2) on a two dimensional Cartesian plane. If we connect A and B then we get line segment AB. But if we connect AB and extend it on both side at infinite length then we get line AB.

Input

The input file contains several sets of inputs. The description of each set of input is given below:

The description for each set of input is given in two lines. Each line contains four integers and a string. First line contains x1, y1, x2, y2 and S1 and the second line contains x3, y3, x4, y4 and S2. The value of S1 and S2 can be either “L” or “LS” which stands for “Line” and “Line-segment” respectively. (x1, y1) and (x2, y2) are the endpoints of first line segment or they are just two different points on the first line depending on the value of S1. The same story applies for the second input line for this set. Input is terminated by a set where the value of S1 and S1 is “END”. This set should not be processed. Point (x1,y1) and (x2,y2) are always different. Similarly point (x3,y3) and (x4,y4) are also always different. All the integers in the input file have absolute value less than 101.

Output

For each set of input you should produce one line of output which contains a single floating-point number indicating the distance between the two lines or line segments or the distance between one line and one line segment. This floating-point number contains five digits after the decimal point. Errors less than 2e-5 will be ignored.

Sample Input

1
2
3
4
5
6
10 10 20 20 L
-10 –10 19 19 L
10 10 12 13 LS
11 11 19 20 LS
10 10 12 12 END
11 11 23 34 END

Output for Sample Input

1
2
0.00000
0.27735

Solution

題目描述：

詢問 線段/線 和 線段/線 之間的最短距離為何。

題目解法：

據說這一題精準度卡很緊，上一次是在兩年前寫這一題，那是使用投影判斷，果真死在精度？

總之，為了避開投影精準度問題，使用外積和內積來判斷我們所有需要的條件。

  • 兩線斷是否相交
  • 一個點是否在線段兩端點之間 (線段上方/下方)
  • 是否在線段上

以上三點接能只靠加減乘來完成，由於輸入值都是整數，不會有精度上的問題。

接著，個別討論所有配對情況要如何判斷。

  • 線段與線段
    • 相交，最鄰近距離 0。
    • 不相交，查閱是否能作投影，否則直接查閱到端點的距離。
  • 線與線
    • 不平行，最鄰近距離 0。
    • 平行，直接調用公式計算兩線距離。 // 當然可以調用投影距離。
  • 線與線段
    • 線段跨過線的兩側，最鄰近距離 0
    • 同側，直接做投影。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double closest(LINE2D l1, LINE2D l2) {
    if(l1.type == SEGMENT && l2.type == SEGMENT) {
        if(intersection(l1.s, l1.e, l2.s, l2.e))
            return 0;
        double c = 1e+30;
        if(between(l1.s, l1.e, l2.s))
            c = min(c, distProjection(l1.s, l1.e, l2.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l1.s, l1.e, l2.e))
            c = min(c, distProjection(l1.s, l1.e, l2.e));
        else
            c = min(c, min(dist(l1.s, l2.e), dist(l1.e, l2.e)));
        /* opposite */
        if(between(l2.s, l2.e, l1.s))
            c = min(c, distProjection(l2.s, l2.e, l1.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l2.s, l2.e, l1.e))
            c = min(c, distProjection(l2.s, l2.e, l1.e));
        else
            c = min(c, min(dist(l2.s, l1.e), dist(l2.e, l1.e)));
        return c;
    }
    if(l1.type == LINE && l2.type == LINE) {
        int a1, a2, b1, b2, c1, c2;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        a2 = l2.s.y - l2.e.y;
        b2 = l2.e.x - l2.s.x;
        c2 = - (a2 * l2.s.x + b2 * l2.s.y);
        if(a1 * b2 - a2 * b1 != 0)
            return 0;
        return distProjection(l1.s, l1.e, l2.s);
    }
    if(l1.type != l2.type) {
        if(l1.type == SEGMENT)
            swap(l1, l2);
        /* l1 LINE, l2 SEGMENT*/
        int a1, b1, c1;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        int v1, v2;
        v1 = a1 * l2.s.x + b1 * l2.s.y + c1;
        v2 = a1 * l2.e.x + b1 * l2.e.y + c1;
        if(v1 * v2 <= 0)
            return 0; // different side
        return min(distProjection(l1.s, l1.e, l2.s), distProjection(l1.s, l1.e, l2.e));
    }
    return -1;
}
int main() {
    // freopen("in.txt", "r+t", stdin);
    // freopen("out.txt", "w+t", stdout); 
    int x1, x2, y1, y2;
    LINE2D l1, l2;
    char s[1024];
    while(scanf("%d %d %d %d %s", &x1, &y1, &x2, &y2, s) == 5 && s[0] != 'E') {
        l1.s = Pt(x1, y1), l1.e = Pt(x2, y2);
        if(!strcmp("L", s))
            l1.type = LINE;
        else
            l1.type = SEGMENT;
        scanf("%d %d %d %d %s", &x1, &y1, &x2, &y2, s);
        l2.s = Pt(x1, y1), l2.e = Pt(x2, y2);
        if(!strcmp("L", s))
            l2.type = LINE;
        else
            l2.type = SEGMENT;
        double ret = closest(l1, l2);
        printf("%.5lf\n", ret);
    }
    return 0;
}
/*
10 10 20 20 L
-10 -10 19 19 L
10 10 12 13 LS
11 11 19 20 LS
1 1 2 2 LS
3 3 4 4 LS
1 1 2 2 LS
3 3 4 4 L
10 10 12 12 END
11 11 23 34 END
*/