11662 (삼분탐색 ternary search)
민호와 강호 : https://www.acmicpc.net/problem/11662
참조 사이트 :
1. https://conpulake.tistory.com/29
삼분 탐색이란 개념을 처음 알게되었다.
범위를 lo, hi 구간으로 잡고 p, q 라는 구간을 설정한다.
p는 1/3지점 , q는 2/3지점을 나타낸다.
p = (hi - lo) / 3 + lo = (hi + 2lo)/3
q = 2*(hi - lo) / 3 + lo = (2hi + lo)/3
삼분 검색의 경우, 아래로 볼록 하거나 위로 볼록한 형태의 구간에서 사용 가능하다고 한다.
정확하게는 더 공부를 해봐야겠으나, 일반적인 2차 함수의 구간을 나타내는 범위에 사용 가능할 것으로 보인다.
우선, 문제를 이해하기 위해 시간에 따른 민호와 강호 사이의 거리를 구하는 식은 아래와 같다.
문제를 처음에 해석하는데 살짝 애를 먹긴했는데.. 다음과 같이 구할 수 있다.
A 점에서 B점으로 이동하는데 걸리는 시간을 1초라고 생각하고, 시간의 resolution을 10^6으로 생각하면, AB 사이의 거리는 속도가 된다.
속도 * 10^-6*t (0<= t<=10^6)를 해주면 변위가 되므로 원래 위치에서 더해주면 t 시점의 위치가 된다.
민호의 위치 = A의 위치 + (B의 위치 - A의 위치)* 시간
강호의 위치 = C의 위치 + (D의 위치 - C의 위치)* 시간
이를 f()메소드에 구현하였으며, 시간을 삼분탐색할 값으로 선정하였다.
이해한 바에 따라 hi 및 lo 범위를 축소 시키면 일정 범위 이하로는 줄어들지 않아 무한루프에 빠지거나
정확도가 떨어지는 현상이 발생한다고 한다.
현 문제에서는 hi-lo 의 값이, 최소 단위인 1e-6보다 작아지는 경우, 루프를 빠져나오고,
구해진 hi-lo 를 순회하여 min 값을 구해 답을 찾았다.
hi 값이 변하면 답이 크게 틀어지는 것으로 보아, 범위 설정에 따라 값이 어떻게 변하는지 더 스터디가 필요할 것 같다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int N, M;
static boolean DBG = false;
static double[] x, y;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
x = new double[4];
y = new double[4];
for (int i = 0; i < 4; i++) {
x[i] = Double.parseDouble(st.nextToken());
y[i] = Double.parseDouble(st.nextToken());
}
//10^6 == 1e6
//10^-6 == 1e-6
double lo = 0;
double hi = 1e6;
while (hi - lo >= 1e-6) {
double p = (hi + 2 * lo) / 3;
double q = (2 * hi + lo) / 3;
if (f(p) >= f(q))
lo = p;
else
hi = q;
if (DBG)
System.out.printf("lo: %f hi : %f\n", lo, hi);
}
double answer = Double.MAX_VALUE;
for (int i = (int) lo; i <= hi; i++) {
answer = Math.min(f(i), answer);
}
bw.write(String.format("%f\n", answer));
br.close();
bw.close();
}
private static double f(double time) {
double nx1 = x[0] + (x[1] - x[0]) * time * 1e-6;
double ny1 = y[0] + (y[1] - y[0]) * time * 1e-6;
double nx2 = x[2] + (x[3] - x[2]) * time * 1e-6;
double ny2 = y[2] + (y[3] - y[2]) * time * 1e-6;
return getDistance(nx1, nx2, ny1, ny2);
}
private static double getDistance(double x1, double x2, double y1, double y2) {
return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
}
}