[ 백준 ] 11662 / 민호와 강호

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
115/228
post-thumbnail

# Appreciation

/*
 * Problem :: 11662 / 민호와 강호
 *
 * Kind :: Brute Force
 *
 * Insight
 * - 처음에는 점과 직선사이의 최단거리를 구하는 것인가 싶었지만...
 *   점과 점이 시간에 따라 이동하고 그 두 점 사이의 거리를 구해야 되는거라 어렵겠다 싶었다
 *
 * - 절대/상대 오차가 10e-6 까지 허용되는 것을 보고,
 *   그냥 다 해봐야 겠다고 생각했다
 *   # O(10^6) 정도면 1초 안에 계산할 수 있다
 *   # 보통 double 의 경우 15 자리정도 정밀도를 가지니까 괜찮다 싶었다
 *   # 구간을 허용해주는 오차를 단위길이로 하여 구했다
 *
 * Point
 * - 삼분탐색을 이용해서 구할 수도 있다고 한다
 *   나중에 삼분탐색도 공부해서 이 문제를 그렇게도 풀어봐야겠다
 * 
 * - double std = 10e-6 으로 해서
 *   DM *= std; DG *= std; 로 할 수도 있지만
 *   이 경우 틀렸습니다가 나온다
 *   + 아무래도 double std = 10e-6 를 이렇게 선언하는 데서
 *     예상치 못한 오차가 추가로 발생하여 그런 것 같다
 *     # 실제로 double std = 10e-6 으로 선언한 후 
 *       cout << std << endl; 로 출력해보면
 *       10e-5 가 나온다 (cout << fixed; cout.precision(10) 을 해도 마찬가지)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { double y, x; };

// Set up : Functions Declaration
double getDist(const Point &u, const Point &v);
Point operator + (Point u, Point v);
Point operator - (Point u, Point v);
Point operator * (Point p, int v);
Point& operator /= (Point &p, int v);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    Point A{}, B{}, C{}, D{};
    cin >> A.x >> A.y;
    cin >> B.x >> B.y;
    cin >> C.x >> C.y;
    cin >> D.x >> D.y;

    // Process
    int std = 10e6; /* 허용 오차 */
    Point DM = B - A; /* 민호의 단위길이 */
    DM /= std;
    Point DG = D - C; /* 강호의 단위길이 */
    DG /= std;

    double ans = numeric_limits<double>::max();
    for (int i=0; i<=10e6; i++) {
        Point CM = A + (DM * i); /* 민호의 시작지점 + 민호의 단위길이 * offset */
        Point CG = C + (DG * i); /* 강호의 시작지점 + 강호의 단위길이 * offset */
        ans = min(ans, getDist(CM, CG));
    }

    // Control : Output
    cout << fixed; /* cout 의 소수점 출력 */
    cout.precision(10); /* 10자리 까지 */
    cout << ans << endl;
}

// Helper Functions
double getDist(const Point &u, const Point &v)
/* 두 좌표간의 거리를 반환 */
{
    double dx = u.x - v.x;
    double dy = u.y - v.y;
    return sqrt(dx*dx + dy*dy);
}

Point operator + (Point u, Point v)
/* 편의를 위해 구현한 좌표끼리의 덧셈 연산 */
{
    return {u.x + v.x, u.y + v.y};
}

Point operator - (Point u, Point v)
/* 편의를 위해 구현한 좌표끼리의 뺄셈 연산 */
{
    return {u.x - v.x, u.y - v.y};
}

Point operator * (Point p, int v)
/* 편의를 위해 구현한 좌표에 (int)v 값을 곱하는 연산 */
{
    return {p.x * v, p.y * v};
}

Point& operator /= (Point &p, int v)
/* 편의를 위해 구현한 좌표에 (int)v 값으로 나누는 연산 */
{
    p.x /= v;
    p.y /= v;
    return p;
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글