백준 문제풀이

BOJ 11563.cpp

#include <bits/stdc++.h>
using namespace std;

int N, M;
struct Point{
    double x1, y1, x2, y2;
    Point(){}
    Point(double a1, double b1, double a2, double b2) : x1(a1), y1(b1), x2(a2), y2(b2){}
};
Point A[2222];
Point B[2222];
// x, y 사이의 거리
double Distance(double x1, double y1, double x2, double y2){
    return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
}
// 벡터 x, y의 내적
double dot(double x1, double y1, double x2, double y2){
    return x1*x2 + y1*y2;
}
// 벡터 x, y의 외적
double cross(double x1, double y1, double x2, double y2){
    return x1*y2 - x2*y1;
}
// 선분 12에 점 3에서 수선의 발을 내릴 수 있으면 수선의 길이, 아니면 -1 리턴
double perpendicular(double x1, double y1, double x2, double y2, double x3, double y3){
    double dot1 = dot(x2-x1, y2-y1, x3-x1, y3-y1);
    double dot2 = dot(x1-x2, y1-y2, x3-x2, y3-y2);
    // 점 3이 선분 12와 예각 2개를 이루면 수선을 내릴 수 있음
    if(dot1*dot2 >= 0)
        return abs(cross(x2-x1, y2-y1, x3-x1, y3-y1)) / Distance(x1, y1, x2, y2);
    return -1;
}
// p1 의 선분 AB 와 p2 의 선분 CD 사이거리
double Path(Point p1, Point p2){
    // 점 A (a1, a2)
    double a1 = p1.x1;
    double a2 = p1.y1;
    // 점 B (b1, b2)
    double b1 = p1.x2;
    double b2 = p1.y2;
    // 점 C (c1, c2)
    double c1 = p2.x1;
    double c2 = p2.y1;
    // 점 D (d1, d2)
    double d1 = p2.x2;
    double d2 = p2.y2;

    // 먼저 모든 점 쌍 사이의 거리가 후보가 될 수 있음
    double dist = Distance(a1, a2, c1, c2), temp;
    dist = min(dist, Distance(a1, a2, d1, d2));
    dist = min(dist, Distance(b1, b2, c1, c2));
    dist = min(dist, Distance(b1, b2, d1, d2));
    // 어느 점에서 다른 선분에 수선을 내릴 수 있으면 수선의 길이도 후보
    temp = perpendicular(a1, a2, b1, b2, c1, c2);
    if(temp >= 0) dist = min(dist, temp);
    temp = perpendicular(a1, a2, b1, b2, d1, d2);
    if(temp >= 0) dist = min(dist, temp);
    temp = perpendicular(c1, c2, d1, d2, a1, a2);
    if(temp >= 0) dist = min(dist, temp);
    temp = perpendicular(c1, c2, d1, d2, b1, b2);
    if(temp >= 0) dist = min(dist, temp);

    return dist;
}
int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> N >> M;
for (int i = 0; i < N; ++i){
    double a, b, c, d;
    cin >> a >> b >> c >> d;
    A[i] = Point(a,b,c,d);
}
for (int i = 0; i < M; ++i){
    double a, b, c, d;
    cin >> a >> b >> c >> d;
    B[i] = Point(a,b,c,d);
}
double ans = -1;
for (int i = 0; i < N; ++i){
    for(int j = 0; j < M; ++j){
        auto p = A[i];
        auto q = B[j];
        if(ans<0) ans = Path(p,q);
        else ans = min(ans, Path(p,q));
    }
}
cout<<fixed;
cout.precision(16);
cout << ans << '\n';

return 0;
}