11664 선분과 점

이분탐색 같은데?? 

 

선분이 주어질 때 최소 길이로 가기 위해 참/거짓 판정을 해야 하는데 어느 방향으로 가야 하냐에서 막혔다. 

분류를 보니 삼분탐색이라 되어 있는데 삼분탐색...? 찾아보니 볼록한 경우에서 최대최소를 찾는 경우에 사용한다.

 

이게 알고보니 선분이 아니라 점과의 거리에 대해서 생각해보면 C에서 거리가 최소고 A, B 방향으로 점이 움직이면서 거리가 멀어지면서 볼록한 함수 형태가 나온다!!! 신기해. 

 

이분탐색은

/---------A---------/----------B--------/

                               mid

 

두 구간을 탐색하는데 삼진탐색은 세 구간을 탐색한다. 

 

/--------A-------/---------B-------/--------C---------/

                          mid1                      mid2

 

 

이제 이진탐색이랑 비슷하게 풀어보자

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    double ax, ay, az, bx, by, bz, cx, cy, cz;
    scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf", &ax, &ay, &az, &bx, &by, &bz, &cx, &cy, &cz);
    
    double mid1, mid2;
    for (int i = 0; i < 1000000; i++) {
        // 3등분 점을 구한다
        double x1 = ax + (bx - ax)/3;
        double x2 = ax + 2 * (bx - ax)/3;
        double y1 = ay + (by - ay)/3;
        double y2 = ay + 2 * (by - ay)/3;
        double z1 = az + (bz - az)/3;
        double z2 = az + 2 * (bz - az)/3;
        
        mid1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) + (z1 - cz) * (z1 - cz);
        mid2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy) + (z2 - cz) * (z2 - cz);
        
        if (mid1 < mid2) {
            bx = x2;
            by = y2;
            bz = z2;
        }
        else {
            ax = x1;
            ay = y1;
            az = z1;
        }
    }
    
    printf("%.9lf", min(sqrt(mid1), sqrt(mid2)));
    
    return 0;
}