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
|
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define maxn 100055
using namespace std;
int t;
const double eps = 1e-8;
int sgn(double x){
if(fabs(x) <= eps) return 0;
return x > 0 ? 1 : -1;
}
struct Point{
double x, y;
Point(){}
Point(double _x, double _y){ x = _x; y = _y; }
Point operator +(const Point &A){
return Point(x + A.x, y + A.y);
}
Point operator -(const Point &A){
return Point(x - A.x, y - A.y);
}
double operator *(const Point &A){
return x * A.x + y * A.y;
}
double operator ^(const Point &A){
return x * A.y - y * A.x;
}
bool operator ==(const Point &A){
return sgn(x - A.x) == 0 && sgn(y - A.y) == 0;
}
double len(){
return sqrt(x * x + y * y);
}
void input(){
scanf("%lf%lf", &x, &y);
}
void print(){
printf("[Point] x:%.2f y:%.2f\n", x, y);
}
}os, ot, ts, tt;
struct Line{
Point s, e;
Line(){}
Line(Point _s, Point _e){ s = _s; e = _e; }
int segcrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
Point crosspoint(Line v){
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
}
bool parallel(Line v){
return sgn((e - s) ^ (v.e - v.s)) == 0;
}
double cosVal(Line v){
double val = (e - s) * (v.e - v.s);
return val / (e - s).len() / (v.e - v.s).len();
}
}l1, l2;
bool check(double x){
Line v = Line(Point(-10005.0, x), Point(10005.0, x));
if(v.segcrossseg(l1) && v.segcrossseg(l2)) return true;
return false;
}
void cal(double x){
int a = x * 1000;
if(a % 10 >= 5) a += 5;
a /= 10;
double b = a / 100.0;
printf("%.2lf\n", b);
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--){
os.input(); ot.input();
ts.input(); tt.input();
if(sgn(os.y - ot.y) > 0) swap(os, ot); l1 = Line(os, ot);
if(sgn(ts.y - tt.y) > 0) swap(ts, tt); l2 = Line(ts, tt);
if(os == ot || ts == tt || !l1.segcrossseg(l2)){
printf("%.2f\n", 0 + eps);
}
else if((l1.parallel(Line(Point(0, 0), Point(1, 0))) || l2.parallel(Line(Point(0, 0), Point(1, 0))))){
printf("%.2f\n", 0 + eps);
}
else if(l1.parallel(l2)){
printf("%.2f\n", 0 + eps);
}
else{
Point m = l1.crosspoint(l2);
double lf = m.y, rt = 10005.0;
while(sgn(rt - lf) > 0){
double mid = (lf + rt) * 0.5;
check(mid) ? lf = mid : rt = mid;
}
Point v1 = Line(Point(-10005.0, lf), Point(10005.0, lf)).crosspoint(l1);
Point v2 = Line(Point(-10005.0, lf), Point(10005.0, lf)).crosspoint(l2);
if(sgn(l1.e.y - l2.e.y) <= 0 && Line(v1, Point(v1.x, 10005)).segcrossseg(l2)){
printf("%.2f\n", 0 + eps);
continue;
}
else if(sgn(l2.e.y - l1.e.y) <= 0 && Line(v2, Point(v2.x, 10005)).segcrossseg(l1)){
printf("%.2f\n", 0 + eps);
continue;
}
else if(sgn(fabs((v1 - m) ^ (v2 - m)) * 0.5) == 0){
printf("%.2f\n", 0 + eps);
continue;
}
cal(fabs((v1 - m) ^ (v2 - m)) * 0.5 + 1e-6);
}
}
return 0;
}
|
