2022 사다리

 

보자마자 수학문제인 줄 알고 열심히 식 세워보려다가 포기했다. 알고보니 이분탐색으로 c를 찾는 문제였음. 

 

아무튼.. 

 

이분탐색이라는 걸 알아도 너무 어려웠다. 식 만드는 게 특히ㅜㅜ 어느 부분을 탐색할지 정하는 것도 애매하고 c를 구하는 식 세우는 것도 어렵고.. 

 

 

 

어찌저찌 구하긴 구했다. 그래도 전에 실수 이분탐색 문제를 풀어봐서 좀 편했다. 

 

그렇습니다

 

int main()
{
	int n;
	scanf("%d", &n);

	vector<i64> x(n), v(n);

	for (int i = 0; i < n; i++)
		scanf("%lld", &x[i]);

	for (int i = 0; i < n; i++)
		scanf("%lld", &v[i]);

	double lo = 0, hi = 1e9;

	for (int i = 0; i < 100; i++)
	{
		double mid = (lo + hi) * 0.5;

		vector<double> starts, ends;
		for (int j = 0; j < n; j++)
		{
			starts.push_back(x[j] - v[j] * min((double)x[j] / v[j], mid));
			ends.push_back(x[j] + v[j] * min((1e9 - x[j]) / v[j], mid));
		}

		if (*max_element(all(starts)) > *min_element(all(ends)))
			lo = mid;
		else
			hi = mid;
	}

	printf("%.10lf", lo);

	return 0;
}

 

그 때 사용했던 코드가 이거라서 참고해서 코딩했다. 

 

아래는 내가 짰던 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

double calc(double x, double y, double d)
{
    double h1 = sqrt(x*x - d*d);
    double h2 = sqrt(y*y - d*d);
    
    return h1*h2/(h1+h2);
}

int main() {
    double x, y, c;
    scanf("%lf %lf %lf", &x, &y, &c);
    
    double lo = 0.0, hi = min(x, y);
    
    for (int i = 0; i < 100; i++)
    {
        double mid = (lo + hi) * 0.5;
        
        if (calc(x, y, mid) < c)
            hi = mid;
        else
            lo = mid;
    }
    
    printf("%.6lf\n", lo);
    
    return 0;
}