C++ / 백준 / 11662 / 민호와 강호

문제

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

11662번: 민호와 강호

문제풀이

민호의 시작 좌표 x, y를 m_start_x, m_start_y, 도착 좌표를 m_end_x, m_end_y로 두고 강호는 m->g로 바꿔서 둔다.

삼분 탐색의 1/3 지점은 mid1로, 2/3 지점은 mid2로 둔다.

오차가 10^-6까지 허용한다고 되어있으나 100번 정도 돌리면 어느 정도는 오차가 적을 거라 생각해서 100번만 돌리도록 했다.

거리를 나타낸 2차식에서 왼쪽은 서로의 시작 지점을 비교한 값, 오른쪽은 서로의 끝점을 비교한 값으로 둔다.

mid1값이 더 크면 시작 지점의 x, y좌표들을 mid1값으로 옮기고, mid2 값이 더 크면 종료지점의 x, y좌표들을 mid2값으로 옮긴다.

백준에서 출력 예제를 보면 소수 10자리까지 출력을 하길래 소수 10자리까지 출력하도록 추가 설정을 했다.

 

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

double Start(double start, double end) {
	return start + (end - start) / 3;
}

double End(double start, double end) {
	return end - (end - start) / 3;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	double m_start_x = 0, m_start_y = 0;
	double m_end_x = 0, m_end_y = 0;

	double g_start_x = 0, g_start_y = 0;
	double g_end_x = 0, g_end_y = 0;

	cin >> m_start_x >> m_start_y >> m_end_x >> m_end_y >> g_start_x >> g_start_y >> g_end_x >> g_end_y;

	int T = 100;

	double mid1 = 0, mid2 = 0;

	while (T--) {
		mid1 = sqrt(pow(m_start_x - g_start_x, 2) + pow(m_start_y - g_start_y, 2));
		mid2 = sqrt(pow(m_end_x - g_end_x, 2) + pow(m_end_y - g_end_y, 2));

		if (mid1 > mid2) {
			m_start_x = Start(m_start_x, m_end_x);
			m_start_y = Start(m_start_y, m_end_y);
			g_start_x = Start(g_start_x, g_end_x);
			g_start_y = Start(g_start_y, g_end_y);
		}
		else if (mid1 < mid2) {
			m_end_x = End(m_start_x, m_end_x);
			m_end_y = End(m_start_y, m_end_y);
			g_end_x = End(g_start_x, g_end_x);
			g_end_y = End(g_start_y, g_end_y);
		}
		else {
			break;
		}
	}
	cout << fixed;
	cout.precision(10);
	cout << min(mid1, mid2);
}