[코드포스 Practice8] E. The Meeting Place Cannot Be Changed

The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.

Bytecity에 있는 메인로드는 남쪽에서 북쪽으로 일직선이다. 편리하게, 가장 남쪽의 건물에서 북쪽 방향으로 미터로 측정된 좌표가 있다. 

At some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.

도로의 몇 지점에는 n명의 친구가 있다. 그리고 그들의 i번째는 xi미터 지점에 서있다. 남쪽 또는 북쪽 어느 두 방향으로 움직일 수 있다. vi 이하의 어느 속도로도 움직일 수 있다. 

You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate.

너는 도로의 같은 지점에 n명의 친구들 모두 같이 모일 최소 시간을 계산해야 한다.  *그들이 정수 좌표에 만날 필요는 없다 (그럼 정수 좌표는 왜있지?)

 

Input
The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.

첫번째 줄은 하나의 정수 n을 포함한다. -- 친구의 수

The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 109) — the current coordinates of the friends, in meters.

두번째 줄은 n개의 정수 x1, x2, x3 .. xn을 포함한다. -- 친구의 최근 좌표 (미터단위의)

The third line contains n integers v1, v2, ..., vn (1 ≤ vi ≤ 109) — the maximum speeds of the friends, in meters per second.

세번째 줄은 n개의 정수 v1, v2, v3 ... vn을 포함한다 -- 친구의 최대 속도 (미터/초)

Output
Print the minimum time (in seconds) needed for all the n friends to meet at some point on the road.

n명의 친구들 모두가 도로의 어느 지점에서 만나기 위한 최소 시간을 출력해라

Your answer will be considered correct, if its absolute or relative error isn't greater than 10 - 6. Formally, let your answer be a, while jury's answer be b. Your answer will be considered correct if

 holds.

 

 

 

---

 

최대최소 위치로 중간점 잡고 중간점으로 이동 -> 다시 중간점 잡고 -> 이동

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sortbyFirst(pair<int,int> &a, pair<int,int> &b){
    return (a.first < b.first);
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i].first);
    
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i].second);
    
    for(int i = 0; i < 5; i++){
        sort(v.begin(), v.end(), sortbyFirst);
        double mid = (double)v[0]/2 + (double)v[n-1]/2;
        for(int i = 0; i < n; i++){
            
        }
    }
    
    return 0;
}

 

이렇게 하면 될 것 같아서 코드 짜고 있었는데 생각해보니깐 속도가 1이고 위치가 1, 10^9이라면 반복문 10^9번 반복한다ㅋㅋ 게다가 이중 for문이라서 시간 더 걸림.. ㅎㅎ 다른 방식으로 생각해봐야겠다. 

 

 

---

 

이분탐색 힌트 받아서 낑낑거리다가 막혀서 포기..

쫀심 회복으로 백준 쉬운문제 좀 풀다가(ㅋㅋ농담임) 다시 풀어보려다 결국 모르겠어서 다시 힌트 받았다.

 

 

아 이게 일단 시간을 구하기 때문에 시간을 기준으로 이분탐색을 한다. 그리고 이 문제를 범위로 생각하면 구하기 쉽다. t=2일때 a점의 범위.. 아무튼 겹치는 범위의 최소를 구하면 된다. 

 

 

 

 

 

어떻게 짤지는 다 생각해놨고 이제 코딩만 하면 된다. 이건 내일로.. 너무 졸림 zz

 

 

---

으아악

왤케 어려워!

 

범위 확인하는 부분에서 막혔다.

bool isOk(double mid, int n, vector<pair<int, int>> v){
    double val1_left = v[0].first;
    double val1_right = v[0].first + v[0].second*mid;
    
    printf("\nval1 : %lf %lf\n", val1_left, val1_right);
    for(int i = 1; i < n; i++){
        double val2_left = max((double)v[0].first, (double)v[i].first - v[i].second*mid);
        double val2_right = min((double)v[n-1].first, (double)v[i].first + v[i].second*mid);
        printf("val2 : %lf %lf\n", val2_left, val2_right);
        
        if((val1_left < val2_left) && (val2_left > val1_right))
            return false;
        if((val1_left > val2_left) && (val1_left > val2_right))
            return false;
    }
    
    return true;
}

위에 적은 것처럼 하면 예외가 있어서 이렇게 코드를 바꿨다.

 

잘 돌아가는가 싶더니 또 이상하게 돌아감..

 

알고보니 이런 경우는 맞다고 하게 된다.

으아악

악

으아악

 

헝

헝헝

 

다시 고민해봐야겠다. 이거 잘못하면 여기서 n^2 나겠는데

---

bool isOk(double mid, int n, vector<pair<int, int>> v){
    double val1_left = v[0].first;
    double val1_right = v[0].first + v[0].second*mid;
    
    printf("\nval1 : %lf %lf\n", val1_left, val1_right);
    
    for(int i = 1; i < n; i++){
        double val2_left = max((double)v[0].first, (double)v[i].first - v[i].second*mid);
        double val2_right = min((double)v[n-1].first, (double)v[i].first + v[i].second*mid);
        printf("val2 : %lf %lf\n", val2_left, val2_right);
        
        if(val1_left < val2_left)
            val1_left = val2_left;
        if(val2_right < val1_right)
            val1_right = val2_right;
        
        if((val1_left < val2_left) && (val2_left > val1_right))
            return false;
        if((val1_left > val2_left) && (val1_left > val2_right))
            return false;
    }
    
    return true;
}

 

으음 다음으로 범위를 자르면 어떨까 생각해서 이렇게 코드를 짰는데 끝도없이 true가 나왔다. 문제가 있을 것 같은데 찾아봐야지 다시..

 

 

---

 

 

결국 풀이 봤다ㅋㅋ

범위 때문에 애 먹었는데 이렇게 하구나

간단해서 조금 눈물이 난다

 

다 풀고 생각해보니깐 실수 범위에서 이분탐색은 그냥 O(1)이구나. 범위 구하는 부분에서 O(n)이 걸려서 결국 100N이 걸렸다. 신기방기

 

또 100번 도는 이유가 오차 범위가 10^-6, 10^-9이기 때문에 10^9를 100번 이분탐색 하면 10^9 * 2^-100 이 되어 아주아주 숫자가 작아진다. 궁금해서 곱해봤는데 2를 한 40번 나누니깐 10^-6을 넘어섰다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long int;

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<i64, i64>> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i].first);
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i].second);
    
    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(v[j].first - v[j].second * min((double)v[j].first / v[j].second, mid));
            ends.push_back(v[j].first + v[j].second * min((1e9 - v[j].first) / v[j].second, mid));
        }
        
        if(*max_element(starts.begin(), starts.end()) > *min_element(ends.begin(), ends.end()))
            lo = mid;
        else
            hi = mid;
    }
    
    printf("%.10lf", lo);
    
    
    return 0;
}

 

 

이번 문제도 이렇게 끝~