BOJ 11662번 민호와 강호

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

github : https://github.com/junho0956/Algorithm/blob/master/11662/11662/%EC%86%8C%EC%8A%A4.cpp

 

삼분탐색의 기본개념을 통해 구현하였으며 설명은 코드에 주석처리 해놓았으니 참고하시면 될 것 같습니다.

삼분탐색 기본개념 : https://junho0956.tistory.com/128?category=869180

 

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
typedef pair<double, double> pii;
 
// x -> 0 // y -> 1
// start : 시작점 end : 끝점
int minho_start[2], minho_end[2];
int kangho_start[2], kangho_end[2];
 
pii minho_move(double p) {
    return make_pair(minho_start[0] + (minho_end[0] - minho_start[0]) * (p / 100), minho_start[1] + (minho_end[1] - minho_start[1]) * (p / 100));
}
 
pii kangho_move(double p) {
    return make_pair(kangho_start[0] + (kangho_end[0] - kangho_start[0]) * (p / 100), kangho_start[1] + (kangho_end[1] - kangho_start[1]) * (p / 100));
}
 
int main() {
    scanf("%d%d%d%d", &minho_start[0], &minho_start[1], &minho_end[0], &minho_end[1]);
    scanf("%d%d%d%d", &kangho_start[0], &kangho_start[1], &kangho_end[0], &kangho_end[1]);
 
    double first_percent = 0, last_percent = 100, length = sqrt(pow(10000, 2) + pow(10000, 2));
    // 오차는 10^-6 까지 허용한다는 것은 ...
    // 10^-6 까지는 맞춰야된다는 건가? 그럼 10^-7 까지의 오차만 확인해본다면
    while (last_percent - first_percent >= 1e-7) {
        double p1, p2;
        // 삼등분 했을 때 좌표
        p1 = (2 * first_percent + last_percent) / 3, p2 = (first_percent + 2 * last_percent) / 3;
 
        // p1 과 p2 를 이용하여 p1 , p2 만큼 이동했을 때 민호와 강호의 좌표를 구함
        // m1 -> minho_move_p1, m2 -> minho_move_p2 , k1, k2 ,,
 
        pii m1 = minho_move(p1), m2 = minho_move(p2);
        pii k1 = kangho_move(p1), k2 = kangho_move(p2);
 
        // 구해야하는 것은 민호와 강호의 p1, p2 만큼 이동했을 때의 거리
        // p1 에 의한 거리
        double len_p1 = sqrt(pow(m1.first - k1.first, 2) + pow(m1.second - k1.second, 2));
        double len_p2 = sqrt(pow(m2.first - k2.first, 2) + pow(m2.second - k2.second, 2));
 
        length = min(min(len_p1, len_p2), length);
 
        // 삼분탐색 조건에 따라서
        // 만약 len_p1 의 길이가 len_p2 의 길이보다 작다면 len_p2 쪽에는 최소값이 없으므로
        if (len_p1 <= len_p2) last_percent = p2;
        else first_percent = p1;
    }
    // 오차가 10^-6 까지는 허용    => 10^-6 까지는 검사 ==> 10^-7 까지만 출력해보면 
    printf("%.7f", length);
 
    return 0;
}