AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D

# # Solution

// Distance of a segment and a point
double p2Seg(Vector2 start_, Vector2 end_, Vector2 p) {
if ((p - start_).dot(end_ - start_) < 0.0) return (p - start_).length();
if ((p - end_).dot(start_ - end_) < 0.0) return (p - end_).length();
return abs((end_ - start_).cross(p - start_)) / (end_ - start_).length();
}

double distance(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4) {
// Distance is 0 if 2 segments cross each other.
double t3 = (p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x);
double t4 = (p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x);
double t1 = (p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x);
double t2 = (p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x);
if (t3 * t4 < 0 && t1 * t2 < 0) return 0.0;

// Distance is the min of 4 distances of 4 points and 2 segments.
double min_ = -1;
min_ = min<double>(p2Seg(p1, p2, p3), p2Seg(p1, p2, p4));
min_ = min<double>(min_, p2Seg(p3, p4, p1));
min_ = min<double>(min_, p2Seg(p3, p4, p2));
return min_;
}

#define MAX_N 1001
Int N;
Vector2 p1, p2, p3, p4;

void input() {
cin >> N;
while (cin >> p1 >> p2 >> p3 >> p4) {
cout << distance(p1, p2, p3, p4) << endl;
}
}

int main() {
cout.precision(15);
input();
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!