백준 11662번 - 민호와 강호(C++/삼분탐색)

https://www.acmicpc.net/problem/11662

11662번: 민호와 강호

 

문제

민호와 강호가 2차원 좌표 평면 위에 있다.
민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다.
민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다.또, 두 사람은 항상 일정한 속도로 걸어간다.
두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.

접근법

처음 접근할때는 한점을 정해두고, 그 값보다 작으면 A구간 크면 B구간으로 쪼개서 진행하는 이분탐색을 사용하려 했지만, 이분탐색은 일단 정렬되어 있어야 하는 자료들에 사용할 수 있다는 사실을 까먹고 있었다.

 

이럴때는 삼분탐색을 사용해야한다. 삼분탐색은 그래프의 형태가 오목하거나 블록할때 (극값은 하나여야한다) 최대, 최소값을 찾기위해 사용되는 기법이다.

 

서로 직선의 거리를 가기때문에, 거리를 이용해 그래프를 그려보자면 극값이 하나인 그래프가 나올것이다. (서로 두 점 사이를 이동하기 때문에)

 

극값이 하나인 그래프에서 양 끝점(low, high)을 기준으로 1:2, 2:1 로 나눈점을 p,q라고 한다.

f(p), f(q) 의 값을 비교해봤을때 f(p)가 더 크면 low ~ p 사이에는 최소값이 없으므로 low = p; 

f(q) 가 더크면 q ~ high 사이에는 최소값이 없으므로 high = q를 

문제의 조건인 1e-6까지 반복해준다. 

 

코드

/*
민호와 강호가 2차원 좌표 평면 위에 있다.
민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다.
민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다.또, 두 사람은 항상 일정한 속도로 걸어간다.
두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.

*/
#include <iostream>
#include <math.h>

using namespace std;
double getDistance(double x1, double y1, double x2, double y2)
{
	return sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)));
}

int main()
{
	double x1, x2, x3, x4, y1, y2, y3, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	cout.precision(10);

	double offset = 0.00;
	double min = 100000;
	double low = 0, high = 100,p,q;
	while (high - low >= 1e-6)
	{
		p = (2 * low + high) / 3; // 1:2 구간
		q = (low + 2 * high) / 3; // 2:1 구간

		double dist_p = getDistance(x1 + (x2 - x1) * (p / 100), y1 + (y2 - y1) * p / 100, x3 + (x4 - x3) * (p / 100), y3 + (y4 - y3) * (p / 100));
		double dist_q = getDistance(x1 + (x2 - x1) * (q / 100), y1 + (y2 - y1) * q / 100, x3 + (x4 - x3) * (q / 100), y3 + (y4 - y3) * (q / 100));
		if (dist_p > dist_q)
		{
			low = p;
		}
		else
		{
			high = q;
			
		}
		min = std::min(min, std::min(dist_p, dist_q));
	}
	cout << min;
}

 

 

이번에는 좀 오래 고민하다 안풀려 구글링으로 힌트를 얻었다. 

여러 문제를 풀어보며, 경험을 좀 더 쌓아야 겠다.