-
Notifications
You must be signed in to change notification settings - Fork 12
/
distance_two_segments.cpp
140 lines (123 loc) · 4.91 KB
/
distance_two_segments.cpp
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
//
// 線分と線分の距離
//
// verified:
// AOJ Course CGL_2_D Segments/Lines - Distance
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D&lang=jp
//
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
//------------------------------//
// 基本要素 (点, 線分)
//------------------------------//
using DD = double;
const DD INF = 1LL<<60; // to be set appropriately
const DD EPS = 1e-10; // to be set appropriately
const DD PI = acosl(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}
/* Point */
struct Point {
DD x, y;
Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}
/* Line */
struct Line : vector<Point> {
Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
this->push_back(a);
this->push_back(b);
}
friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};
//------------------------------//
// 円や直線の交差判定, 距離
//------------------------------//
/*
ccw を用いている
P: point
L: Line
S: Segment
distancePL は、「点」と「直線」の距離
distancePS は、「点」と「線分」の距離
*/
int ccw_for_dis(const Point &a, const Point &b, const Point &c) {
if (cross(b-a, c-a) > EPS) return 1;
if (cross(b-a, c-a) < -EPS) return -1;
if (dot(b-a, c-a) < -EPS) return 2;
if (norm(b-a) < norm(c-a) - EPS) return -2;
return 0;
}
Point proj(const Point &p, const Line &l) {
DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
return l[0] + (l[1] - l[0]) * t;
}
Point refl(const Point &p, const Line &l) {
return p + (proj(p, l) - p) * 2;
}
bool isinterPL(const Point &p, const Line &l) {
return (abs(p - proj(p, l)) < EPS);
}
bool isinterPS(const Point &p, const Line &s) {
return (ccw_for_dis(s[0], s[1], p) == 0);
}
bool isinterLL(const Line &l, const Line &m) {
return (abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
abs(cross(l[1] - l[0], m[0] - l[0])) < EPS);
}
bool isinterSS(const Line &s, const Line &t) {
if (eq(s[0], s[1])) return isinterPS(s[0], t);
if (eq(t[0], t[1])) return isinterPS(t[0], s);
return (ccw_for_dis(s[0], s[1], t[0]) * ccw_for_dis(s[0], s[1], t[1]) <= 0 &&
ccw_for_dis(t[0], t[1], s[0]) * ccw_for_dis(t[0], t[1], s[1]) <= 0);
}
DD distancePL(const Point &p, const Line &l) {
return abs(p - proj(p, l));
}
DD distancePS(const Point &p, const Line &s) {
Point h = proj(p, s);
if (isinterPS(h, s)) return abs(p - h);
return min(abs(p - s[0]), abs(p - s[1]));
}
DD distanceLL(const Line &l, const Line &m) {
if (isinterLL(l, m)) return 0;
else return distancePL(m[0], l);
}
DD distanceSS(const Line &s, const Line &t) {
if (isinterSS(s, t)) return 0;
else return min(min(distancePS(s[0], t), distancePS(s[1], t)), min(distancePS(t[0], s), distancePS(t[1], s)));
}
//------------------------------//
// Examples
//------------------------------//
int main() {
int Q;
cin >> Q;
for (int _ = 0; _ < Q; ++_) {
Point x1, y1, x2, y2;
cin >> x1.x >> x1.y >> y1.x >> y1.y >> x2.x >> x2.y >> y2.x >> y2.y;
Line s(x1, y1), t(x2, y2);
cout << fixed << setprecision(10) << distanceSS(s, t) << endl;
}
}