POJ 2674: Linear World

思いがけないところではまったのでメモ．

概要

線分の上を物体がある方向に向かって動く．2つの物体が衝突すると反対に動く．
一番最後に落ちる物体の名前とその時間を求める．

解法

蟻本の蟻と似た考え方．最後に落ちるものを特定するには，左側にどれだけ落ちる物体があるか数えればいい．左右の位置関係は保存されるので，左側の方にあるのが左側に落ちる．

はまったのは，最小値を0からスタートして，インデックスを-1にしていたこと．
落ちる時間が0のときバグってた．

int N;
double L, V;
char D[32010];
double P[32010];
char str[32010][256];
int main(){
    for(;;){
        scanf("%d", &N);
        if(N == 0) return 0;
        scanf("%lf%lf", &L, &V);
        for(int i = 0; i < N; ++i){
            char buf[8];
            scanf("%s%lf%s", buf, P+i, str[i]);
            D[i] = tolower(buf[0]);
        }
        double res = -eps;
        int idx = -1;
        int l = 0;
        for(int i = 0; i < N; ++i){
            double t = L - P[i];
            if(D[i] == 'n' || D[i] == 'N'){
                t = P[i];
                ++l;
            }
            if(t > res){
                res = t;
                idx = i;
            }
        }
        res /= V;
        if(D[idx] == 'p' || D[idx] == 'P')  idx = l;
        else                                idx = l - 1;
        printf("%13.2f %s\n", (int)(res*100)/100.0, str[idx]);
    }
}