CF 24E: Berland Collider - 二分答案求最早碰撞時間

問題描述

直線上 n 個粒子，給定初始位置 x_i（遞增）和速度 v_i（非零）。正速向右，負速向左。求最早發生碰撞（相向而行）的時間，無碰撞輸出 -1。精度 1e-9。

二分檢查

判斷時間 t 是否已發生碰撞：掃描粒子，維護向右粒子的最大位置 maxRight = max(x_i + t*v_i)。遇到向左粒子，若 x_i + t*v_i <= maxRight 則已碰撞。
二分時間上界 1e10，迭代 100 次或精度滿足即可。注意浮點精度，避免無限循環。

代碼

bool check(double t) {
    double maxR = -1e20;
    for (int i=0; i 0) maxR = max(maxR, pos);
        else if (pos <= maxR) return true;
    }
    return false;
}
int main() {
    while (scanf("%d",&n)==1) {
        for (int i=0;i 1e9) puts("-1");
        else printf("%.20f\n", R);
    }
}