[백준] 11662번 민호와 강호
in Algorithms on BOJ
Ternary Search
문제설명
문제
민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다. 또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.
두 점 (x1, y1), (x2, y2)사이의 거리는 이다.
입력
첫째 줄에 Ax, Ay, Bx, By, Cx, Cy, Dx, Dy가 주어진다. 입력으로 주어지는 모든 좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다.
출력
민호와 강호가 가장 가까웠을 때의 거리를 출력한다. 절대/상대 오차는 10-6까지 허용한다.
접근
이 문제는 민호와 강호 사이의 거리를 시간 t에대한 함수로 구해보면 아래로 볼록한 2차함수 형태가 나온다. 이를 통해 삼분탐색(Ternary Search)문제라는 것을 알 수 있다.
삼분탐색에 관한 자세한 설명은 라이님의 블로그에 자세히 설명되어 있다. 삼분탐색에 관한 내용은 따로 다루지 않겠다.
오차에 대한 조건에 따라 hi와 lo의 오차가 10-6보다 작아질 때 까지 삼분탐색을 수행하였다. (lo p q hi)와 같이 lo ~ hi 사이를 p와 q점을 통해 삼등분을 하고 p점과 q점에서 민호와 강호의 사이 거리를 구한다.
- p점에서의 거리가 q점에서의 거리보다 크면 p를 새로운 lo로 잡는다.
- q점에서의 거리가 p점에서의 거리보다 크면 q를 새로운 hi로 잡느다.
- q점에서의 거리와 p점에서의 거리가 같으면 1번이나 2번을 수행한다.
- 이를 오차범위안에 들어올 때까지 계속해서 반복한다.
코드
#include <iostream>
#include <cmath>
using namespace std;
int a[2], b[2], c[2], d[2];
typedef pair<double, double> POINT;
// A to B
POINT minho(double p){
return {a[0] + (b[0] - a[0])*(p/100), a[1] + (b[1] - a[1])*(p/100)};
}
// C to D
POINT kangho(double p){
return {c[0] + (d[0] - c[0])*(p/100), c[1] + (d[1] - c[1])*(p/100)};
}
int main(){
cin >> a[0] >> a[1] >> b[0] >> b[1] >> c[0] >> c[1] >> d[0] >> d[1];
double lo=0, hi=100, p, q, ans=2*10e4;
while(hi-lo >= 1e-6){
p = (2*lo+hi)/3;
q = (lo+2*hi)/3;
POINT m_p = minho(p);
POINT m_q = minho(q);
POINT k_p = kangho(p);
POINT k_q = kangho(q);
double p_len = pow(m_p.first-k_p.first, 2) + pow(m_p.second-k_p.second, 2);
double q_len = pow(m_q.first-k_q.first, 2) + pow(m_q.second-k_q.second, 2);
p_len = sqrt(p_len);
q_len = sqrt(q_len);
ans = min(ans,min(p_len, q_len));
if(p_len >= q_len)
lo = p;
else
hi = q;
}
cout.setf(ios::fixed);
cout.precision(10);
cout << ans << endl;
}
참고
이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)
