백준 11662 - 민호와 강호

1. 문제 정리
  - 민호와 강호의 좌표가 각 ax, ay, cx, cy의 형태로 주어진다.

  - 민호와 강호는 각각 bx, by, dx, dy의 좌표로 나아간다.

  - 민호와 강호는 같은 시각에 목표 좌표에 도달한다.

  - 민호와 강호의 거리가 가장 가까울 때의 거리값을 출력한다.

  - 절대/상대 오차는 1e-6까지 허용한다.

  - + 예제 출력에서 보이듯 소수점 이하 10째자리까지 출력해보자.
 
2. 접근
  - 처음에 이분탐색으로 풀려다, 검색의 결과 삼분탐색으로 풀 수 있는 문제였다.

  - 시간에 따른 민호와 상호의 거리를 함수화하여 삼분탐색을 실행한다.

  - f(t) = t에 따른 민호와 상호 사이의 거리
 
3. 풀이

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

struct point{
    double x, y;
}typedef point;

point a, b, c, d;
double lo = 0;
double hi = 100;
double ans;
point minho(double p){
    return {a.x + (b.x - a.x) * (p/100), a.y + (b.y - a.y) * (p/100)};
}
point kangho(double p){
    return {c.x + (d.x - c.x) * (p/100), c.y + (d.y - c.y) * (p/100)};
}

double dist(point p1, point p2){
    return sqrt(pow(p1.x-p2.x, 2)+pow(p1.y-p2.y, 2));
}

void ternarySearch(){
    ans = dist({10000,2}, {2,10000});
    while(hi - lo >= 1e-6){
        double p = (lo*2+hi)/3;
        double q = (lo+hi*2)/3;
        point p_m = minho(p);
        point p_k = kangho(p);
        point q_m = minho(q);
        point q_k = kangho(q);
        double dist1 = dist(p_m, p_k);
        double dist2 = dist(q_m, q_k);
        ans = min(ans, min(dist1, dist2));
        if(dist1 > dist2){
            lo = p;
        }
        else {
            hi = q;
        }
    }
}

int main(){
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
    ternarySearch();
    cout.setf(ios::fixed);
	cout.precision(10);
    cout << ans;
}

  - double lo, hi : lo는 하한점, hi는 상한점인데, 여기서 lo가 0이고 hi가 100인 이유는 이후에도 나오지만 민호와 강호가 출발지에서 도착지까지 가는 것을 100으로 하였을 때, 가는 시간을 백분율로 나눈 것이다.

  - point minho(double p), point kangho(double p) : 시간 p(lo와 hi로 구해진)에 따른 민호와 강호의 좌표를 반환한다.

  - double dist(point p1, point p2) : p1, p2좌표에 대한 거리값을 출력한다.

  - void ternarySearch() : 삼분탐색을 실행한다. 문제에서 오차가 1e-6까지 허용된다 하였으므로, 오차는 1e-6으로 while loop 조건에 추가해둔다. p는 lo에 가까운 삼분점, q는 hi에 가까운 삼분점이다. p와 q에 따른 민호와 강호의 거리를 구해주고, 최소값을 ans 변수에 저장한다. dist1 == f(p), dist2 == f(q)로 볼 수 있다. 고로 dist1 > dist2일 경우 lo(하한값)을 q로 바꾸고, dist1 < dist2일 경우 hi(상한값)을 p로 바꾸어, 삼분탐색의 범위를 조정한다.
 
4. 소감

  - 사실 이분탐색도 아직 완전하게 익숙해지지 않은 상황에서 삼분탐색은 이론으로는 쉽지만, 구현하기에는 쉽지 않은 로직이었다.

그래도 꽤나 재밌는 주제를 찾은 것 같아서 흥미롭게 공부했던 기억이 좋게 남았다. 새로운 것을 공부한다는 것은 쉽지만은 않고 재밌지만도 아닌 일이지만, 그래도 이겨내고 고부하는 과정이 재밌다는 것은 즐겁다고 생각한다.

  아래에는 내가 이 문제를 풀면서 도움 받았던 블로그의 주소를 추가하고자 한다. 혹시 나처럼 삼분탐색을 접하는게 처음인 분이 있다면 아래 블로그를 참고해보는 것도 좋을 것 같다.

 

삼분 탐색(Ternary Search)