백준 11662(민호와 강호, 삼분탐색)

문제

---

민호와 강호가 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 이다.

 

 

 

풀이

---

풀이 방법은 많은 것 같다. 나는 시간적인 이우로 삼분탐색을 활용하여 풀었다.

삼분탐색은 이분탐색과 근삿값을 찾아가는 과정이다.

아래로 볼록 위로 볼록과 같은 그래프가 그려지는 방정식에 사용이 가능하다.

최댓값과 최솟값이 존재해야 한다.

 

m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https:%2F%2Fwww.google.com%2F

삼분 탐색(Ternary Search)

이 블로그에서 삼분탐색의 정의에대해 배우고 원리를 이해했다.

 

여기서 1e-6는 문제에서 오차를 1e-6 으로 두어서 오차값을 거기까지 맞추기 위해서 설정한 숫자다.

문제에서 요구하는 정확도에 따라 달라질 수 있는 값이다.

 

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class point{
	public double x, y;
	
	public point(double x, double y){
		this.x = x;
		this.y = y;
	}
}

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static double f(point p1, point p2) {
		return Math.sqrt(Math.pow(p2.y - p1.y, 2) + Math.pow(p2.x - p1.x, 2));
	}
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		String[] number = br.readLine().split("\\s");
		
		point a = new point(Double.parseDouble(number[0]), Double.parseDouble(number[1]));
		point b = new point(Double.parseDouble(number[2]), Double.parseDouble(number[3]));
		point c = new point(Double.parseDouble(number[4]), Double.parseDouble(number[5]));
		point d = new point(Double.parseDouble(number[6]), Double.parseDouble(number[7]));
		
		double low, high, p, q, min=100000000;
		low = 0;
		high = 1000000;
		
		while(high - low >= 1e-6 ) {
			p = ( (2 * low) + high) / 3;
			q = ( low + (2 * high) ) / 3;
			
			point mp = new point(a.x + ((b.x - a.x)* (p / 1000000)),
									a.y + ((b.y - a.y)* (p / 1000000)));
			point mq = new point(a.x + ((b.x - a.x) * (q / 1000000)),
									a.y + ((b.y - a.y)* (q / 1000000)));
			point kp = new point(c.x + ((d.x - c.x)* (p / 1000000)),
									c.y + ((d.y - c.y)* (p / 1000000)));
			point kq = new point(c.x + ((d.x - c.x) * (q / 1000000) ),
									c.y + ((d.y - c.y) * (q / 1000000)));
			
			double fp = f(mp, kp);
			double fq = f(mq, kq);
			
			if(fp > fq) {
				if(min > fq) {
					min = fq;
				}
				low = p;
			}
			else {
				if(min > fp) {
					min = fp;
				}
				high = q;
			
			}
		}
		
		
		System.out.println(min);
	}
}

 

문제 예시에서는 소수점이하 10자리까지 나타냈기에 그렇게 출력을 했더니 답이 틀렸다. 이유는 모르겠지만 그냥 최솟값을 출력해도 될 것 같다.