B11622

개요

백준 문제 11622번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 90분
https://www.acmicpc.net/problem/11622

문제

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

코드

#include <iostream>
#include <cmath>

using namespace std;

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

double calDistance(point A,point B)
{
	return pow(A.x-B.x,2) + pow(A.y-B.y,2);
}
void setPoint(point * A,point * B,point * C,point * D)
{
	int Ax,Bx,Cx,Dx;
	int Ay,By,Cy,Dy;
	cin >> Ax >> Ay >> Bx >> By;
	cin >> Cx >> Cy >> Dx >> Dy;
	A->x = Ax;
	A->y = Ay;
	B->x = Bx;
	B->y = By;
	C->x = Cx;
	C->y = Cy;
	D->x = Dx;
	D->y = Dy;
}

point getPoint(double k,point A,point B)
{
	point resultPoint;
	resultPoint.x = A.x + (B.x - A.x) * (k/100);
	resultPoint.y = A.y + (B.y - A.y) * (k/100);
	return resultPoint; 
}


void solve()
{
	point A,B,C,D;
	setPoint(&A,&B,&C,&D);
	double minResult = 987654321;
	double fp = 0,lp=100,limit=2e9;
	double distA,distB;
	while(lp-fp>=1e-10)
	{
		double k1 = (fp*2 + lp) / 3;
		double k2 = (fp + lp * 2) / 3;
		point curPointAB_1 = getPoint(k1,A,B);
		point curPointCD_1 = getPoint(k1,C,D);
		point curPointAB_2 = getPoint(k2,A,B);
		point curPointCD_2 = getPoint(k2,C,D);
		distA = calDistance(curPointAB_1,curPointCD_1);
		distB = calDistance(curPointAB_2,curPointCD_2);
		minResult = min(minResult,min(distA,distB));
		if(distA >= distB)
		{
			fp = k1;
		}
		else
		{
			lp = k2;
		}


	}
	cout << sqrt(minResult);


}

int main()
{
	cout << fixed;
	cout.precision(6);	
	solve();

}

풀이

이분탐색으로 풀려고 했는데, 이분탐색의 경우 mid값을 정하는데 애매한 부분이 있고
실제로 이 문제에서는 오차문제로 인해 잘 풀리지 않는다.
삼분탐색이나 미적분을 이용한 방법이 있었는데 삼분탐색을 보고 카피해 풀었다.

배울 점, 메모

이분탐색 = 명확한 값 변화가 있을 때
범위,근사값 등이면서 볼록함수 형태 = 삼분탐색