[백준11662] 민호와 강호

백준11662. 민호와 강호

• 민호와 강호의 출발좌표와 도착좌표를 입력받아, 두 사람이 일정한 속도로 도착지점까지 간다고 가정했을때, 두 사람의 최단거리를 구하는 문제이다. (인정 오차는 10^-6)

 

IDEA

양 끝을 경계로 하여 이진탐색을 하면 쉽게 구할 수 있다. 이때 탐색 중단 기준은 좌우 경계의 거리가 10^-6이하인 경우이다.

void getClosestDist(
    double mxl, double myl, double mxr, double myr, 
    double kxl, double kyl, double kxr, double kyr) {
    
    if (getDist(mxl, myl, mxr, myr) < 0.00001 ||
        getDist(kxl, kyl, kxr, kyr) < 0.00001) return;
    
    
    double mxm = (mxl + mxr) / 2;
    double mym = (myl + myr) / 2;
    double kxm = (kxl + kxr) / 2;
    double kym = (kyl + kyr) / 2;
    
    double curr = getDist(mxm, mym, kxm, kym);
    
    if (curr < ret)  {
        ret = curr;
    }

	  getClosestDist(mxl, myl, mxm, mym, kxl, kyl, kxm, kym);    
    getClosestDist(mxm, mym, mxr, myr, kxm, kym, kxr, kyr);    
    
}

• getDist()는 두좌표사이에 거리를 구하는 함수이다.
• 민호(m)와 강호(k)의 각각 왼쪽 좌표, 오른쪽 좌표를 순서대로 입력받아 중점(mxm,mym,kxm,kym)을 구한다.
• 중점일때의 거리를 구하여 만약 이값이 ret보다 작을경우, 업데이트한다.
• 다시 왼쪽, 오른쪽을 나눠 탐색을 진행한다.
• 만약 둘중 한명이라도 양쪽 경계의 거리가 10^-6 이하면 탐색을 종료한다.

이 방식으로 탐색을 하면 결국 모든 경우을 탐색하게 되므로 O(N)이 되어 시간초과가 일어난다.

 

문제점 : 탐색을 오른쪽 왼쪽 모두 하는것 ⇒ 한쪽만 할 순 없을까?

 

중점에서의 거리를 구한 후, 다시 양쪽을 나눠 모두 탐색을하게 되면 사실상 완점 탐색과 다를게 없다. 그렇다면 어떤기준으로 다음 탐색할 부분(왼쪽 OR 오른쪽)을 선택할 수 있을까?

IDEA - IMPROVED

민호와 강호의 시간 t에 대한 거리를 수식으로 표현하면 어떻게 될까? 일단 민호와 강호의 시간에 따른 위치가 t에 대한 1차식으로 표현되므로 아마 민호와 강호의 거리는 t에 대한 2차식에 루트를 씌워놓은 형태가 될것이다. 즉, 이 문제는 2차함수의 최저점을 구하는 문제로 변경된다.

 

2차 함수의 특정 구간에서의 최저점

 

이차함수

 

특정 구간에서의 2차함수의 최저점은 크게 둘중 하나이다

1. 경계점
2. 이차함수의 꼭짓점

즉 경계점(이 문제에서는 출발좌표나 도착좌표)에서 최저가 아니라면 반드시 최저는 이차함수의 꼭짓점에 존재한다. 즉, 우리는 이진탐색과정에서 이차함수의 꼭짓점을 포함하는 부분을 선택해야 하고, 이분할하므로 꼭짓점을 포함하는 부분의 경계가 포함하지 않은 경계보다 반드시 가까울수 밖에 없다. 즉, 최저점을 포함하는 부분의 경계값이 그렇지 않은 경계값보다 작다.

 

 

위의 그림을 보자 Left/Mid/Right를 기준으로 왼쪽과 오른쪽 부분으로 나뉘는걸 볼수 있다. 이때 꼭짓점을 포함하고 있는 부분은 오른쪽이고, 실제 오른쪽 경계(right)의 값이 왼쪽 경계(left)보다 작은것을 볼 수 있다.

 

void getClosestDist(
    double mxl, double myl, double mxr, double myr, 
    double kxl, double kyl, double kxr, double kyr) {
    
    if (getDist(mxl, myl, mxr, myr) < 0.00001 ||
        getDist(kxl, kyl, kxr, kyr) < 0.00001) return;
    
    
    double mxm = (mxl + mxr) / 2;
    double mym = (myl + myr) / 2;
    double kxm = (kxl + kxr) / 2;
    double kym = (kyl + kyr) / 2;
    
    double left = getDist(mxl, myl, kxl, kyl);
    double curr = getDist(mxm, mym, kxm, kym);
    double right = getDist(mxr, myr, kxr, kyr);
    
    if (curr < ret)  {
        ret = curr;
    }
    
    if (left < right) {
        getClosestDist(mxl, myl, mxm, mym, kxl, kyl, kxm, kym);    
    } else {
        getClosestDist(mxm, mym, mxr, myr, kxm, kym, kxr, kyr);    
    }
}

함수는 거의 비슷하나 왼쪽과 오른쪽의 경계에서의 거리를 구한다. 그후 두 값을 비교하여 더 작은쪽의 부분을 탐색한다. 이렇게 되면 탐색을 한쪽씩 줄여나가게 되므로 log2 시간복잡도가 필요하다.

 

Solution

#include <iostream>
#include <cmath>

using namespace std;

// minho : x->y 
// kangho : a->b
double x1, x2, z1, z2, a1, b1, a2, b2;
double getDist(double p1, double q1, double p2, double q2) {
    return sqrt(pow(p2-p1,2) + pow(q2-q1,2));
}

double ret;

void getClosestDist(
    double mxl, double myl, double mxr, double myr, 
    double kxl, double kyl, double kxr, double kyr) {
    
    if (getDist(mxl, myl, mxr, myr) < 0.00001 ||
        getDist(kxl, kyl, kxr, kyr) < 0.00001) return;
    
    
    double mxm = (mxl + mxr) / 2;
    double mym = (myl + myr) / 2;
    double kxm = (kxl + kxr) / 2;
    double kym = (kyl + kyr) / 2;
    
    double left = getDist(mxl, myl, kxl, kyl);
    double curr = getDist(mxm, mym, kxm, kym);
    double right = getDist(mxr, myr, kxr, kyr);
    
    if (curr < ret)  {
        ret = curr;
    }
    
    if (left < right) {
        getClosestDist(mxl, myl, mxm, mym, kxl, kyl, kxm, kym);    
    } else {
        getClosestDist(mxm, mym, mxr, myr, kxm, kym, kxr, kyr);    
    }
}

int main() {
    cin >> x1 >> z1 >> x2 >> z2 >> a1 >> b1 >> a2 >> b2;
    ret = getDist(x1, z1, a1, b1);
    
    getClosestDist(x1, z1, x2, z2, a1, b1, a2, b2);
    cout.precision(11);
    cout << ret;
}