[백준] 11662번 민호와 강호 - C++

출처 : 11662번: 민호와 강호 (acmicpc.net)

11662번: 민호와 강호

---

민호와 강호

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

1273

615

420

49.470%

문제

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

두 점 (x1, y1), (x2, y2)사이의 거리는 (x2−x1)2+(y2−y1)2\(\sqrt{(x2-x1)^2 + (y2-y1)^2}\) 이다.

입력

첫째 줄에 Ax, Ay, Bx, By, Cx, Cy, Dx, Dy가 주어진다. 입력으로 주어지는 모든 좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다.

출력

민호와 강호가 가장 가까웠을 때의 거리를 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1 복사

0 0 1 1 2 2 3 3

예제 출력 1 복사

2.8284271247

예제 입력 2 복사

0 0 1 1 1 0 0 1

예제 출력 2 복사

0.0000000000

예제 입력 3 복사

0 0 10 20 30 0 5 10

 

예제 출력 3 복사

8.2416338387

예제 입력 4 복사

5 5 10 10 7 2 20 30

예제 출력 4 복사

2.8745554697

---

문제 풀이

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<double> pos;
double temp;
// 두 점의 직선거리를 반환
double distance(double x1, double y1, double x2, double y2) {
	return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

int main() {
	for (int i = 0; i < 8; i++) {
		cin >> temp;
		pos.push_back(temp);
	}

	double interval = 1000000.0;
	double dx1 = (pos[2] - pos[0]) / interval;
	double dy1 = (pos[3] - pos[1]) / interval;
	double dx2 = (pos[6] - pos[4]) / interval;
	double dy2 = (pos[7] - pos[5]) / interval;

	int lo = 0.0;
	int hi = interval;

	while (hi - lo >= 3) {
		int mid1 = (2 * lo + hi) / 3;
		int mid2 = (lo + 2 * hi) / 3;

		if (distance(pos[0] + dx1 * mid1, pos[1] + dy1 * mid1, pos[4] + dx2 * mid1, pos[5] + dy2 * mid1) > distance(pos[0] + dx1 * mid2, pos[1] + dy1 * mid2, pos[4] + dx2 * mid2, pos[5] + dy2 * mid2))
			lo = mid1 + 1;
		else
			hi = mid2 - 1;
	}

	double min = distance(pos[0] + dx1 * hi, pos[1] + dy1 * hi, pos[4] + dx2 * hi, pos[5] + dy2 * hi);

	for (int i = lo; i < hi; i++) {
		double dis = distance(pos[0] + dx1 * i, pos[1] + dy1 * i, pos[4] + dx2 * i, pos[5] + dy2 * i);
		if (dis < min)
			min = dis;
	}

	cout << fixed;
	cout.precision(10);
	cout << min;

	return 0;
}