티스토리 뷰

알고리즘 관련/BOJ

BOJ)2022 사다리

JASON 자손9319 2017. 1. 14. 04:01

문제: icpc.me/2022


극혐스러운 수학문제이다.


사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다.


밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다.


사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데


너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
using namespace std;
double x, y, c, lo, hi;
double fx(double ix, double mid) {
    double t = sqrt(x*- mid*mid);
    return t - (t*ix / mid);
}
double gx(double ix, double mid) {
    return mid*ix / sqrt(y*- mid*mid);
}
int main() {
    while (scanf("%lf%lf%lf"&x, &y, &c) != EOF) {
        lo = 0.0;
        hi = min(x, y);
        while (hi - lo > 0.000001) {
            double mid = (lo + hi) / 2.0;
            double cx = gx(c, mid);
            if (fx(cx, mid) > c)
                lo = mid;
            else
                hi = mid;
        }
        printf("%.3lf\n", lo);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9184 신나는 함수 실행  (0) 2017.01.14
BOJ)1049 기타줄  (0) 2017.01.14
BOJ)2022 사다리  (2) 2017.01.14
BOJ)2252 줄 세우기  (0) 2017.01.14
BOJ)1561 놀이 공원  (0) 2017.01.14
BOJ)1666 최대 증가 직사각형 집합  (1) 2017.01.14
댓글
댓글쓰기 폼