Beta Round #24-E: Berland collider

keyword

二分探索　C++

問題概要

区間[-10^9, 10^9]上にN(<5*10^5)個の粒子があり、それぞれ速度v(!=0)で動いている。初めて粒子が衝突する時刻を求めよ。ただし、追い抜きは衝突に含まれない。

解法

答えについて二分探索する。ただし、二分探索の繰り返し回数とかが結構多いので、時刻を決め打ちしたとき衝突するかどうかの判定はO(N)でやらないと落ちる(O(N * logN)も駄目だった)。

感想

入力があらかじめ座標についてソートされた状態で渡されるという条件を見逃したせいで無駄に構造体作ったり無駄にソートしたりしてしまった。

#include <cstdio>
#include <algorithm>
using namespace std;

struct ball{
    double x, v;
    ball(double _x, double _v):x(_x),v(_v){}
    ball(){ball(0,0);}
};

bool operator<(const ball& a, const ball& b){
    return a.x < b.x;
}

const int MAX_N = 500002;
ball balls[MAX_N];
int N;

bool check(double t){
    double rightMost = -1e20;
    for(int i=0; i<N; i++){
        if(balls[i].v > 0){
            rightMost = max(rightMost, balls[i].x + balls[i].v*t);
        }
        else if(rightMost > balls[i].x + balls[i].v*t){
            return true;
        }
    }
    return false;
}

double solve(){
    sort(balls,balls+N);
    double low=0, high=1e10, mid;
    int loop=80;
    while(loop--){
        mid = (low+high)*0.5;
        if(check(mid)) high = mid;
        else low = mid;
    }
    if(high>5e9){
        puts("-1");
        exit(0);
    }
    return mid;
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        double x,v;
        scanf("%lf%lf",&x,&v);
        balls[i] = ball(x,v);
    }
    printf("%.15f\n",solve());
    return 0;
}