SRM-426 500pt: CatchTheMice

keyword

平面幾何　二分探索　C++

問題概要

2次元平面上にN(<50)個の点がありt=0での座標と速度ベクトルが与えられる。max( max(x_i(t)-x_j(t) , i,j in [1..N]), max(y_i(t)-y_j(t), i,j in [1..N]), t>=0)を求める問題。

解法

答えに関して二分探索する。できるかどうかの判定は、自分の解き方だとx_i(t)-x_j(t)が二分探索中の値に等しくなるような時刻を求めて、その時刻で他の点が含まれているかどうか調べてO(N^3)。だけど時刻を挟み撃ちすることでO(N^2)でも解けるらしい。

感想

幾何はライブラリ使うか二分探索か平面走査法か回転でかなりカバーできると思う。

vector<int> xp, yp, xv, yv;
int N;

double largestCage(vector <int> _xp, vector <int> _yp, vector <int> _xv, vector <int> _yv) {
    xp = _xp;
    yp = _yp;
    xv = _xv;
    yv = _yv;
    N = SZ(xp);
    bool same = true;
    int i, j;
    REP(i,N)REP(j,N)if(xv[i]!=xv[j] || yv[i]!=yv[j])same = false;
    if(same){
        return max( (*max_element(ALL(xp))) - (*min_element(ALL(xp))), 
                    (*max_element(ALL(yp))) - (*min_element(ALL(yp)))); 
    }
    double low = 0.0, high = 20000, mid;
    for(int loop=0; loop<100; loop++){
        mid = (low+high)*0.5;
        if(check(mid)) high = mid;
        else low = mid;
    }
    return mid;
}

bool check(double L){
    int i,j,k;
    REP(i,N)REP(j,N)if(i!=j){
        double px = xp[i] - xp[j], py = yp[i] - yp[j];
        int vx = xv[i] - xv[j], vy = yv[i] - yv[j];
        if(vx != 0){
            double t = (L - px)/vx;
            if(t >= 0){
                double minY = 1e10, maxY = -1e10, minX =1e10, maxX = -1e10;
                REP(k,N){
                    minY = min(minY, yp[k]+yv[k]*t);
                    maxY = max(maxY, yp[k]+yv[k]*t);
                    minX = min(minX, xp[k]+xv[k]*t);
                    maxX = max(maxX, xp[k]+xv[k]*t);
                }
                if(maxX - minX < L + EPS && maxY - minY < L + EPS) return true;
            }
        }
        if(vy != 0){
            double t = (L - py)/vy;
            if(t >= 0){
                double minY = 1e10, maxY = -1e10, minX =1e10, maxX = -1e10;
                REP(k,N){
                    minY = min(minY, yp[k]+yv[k]*t);
                    maxY = max(maxY, yp[k]+yv[k]*t);
                    minX = min(minX, xp[k]+xv[k]*t);
                    maxX = max(maxX, xp[k]+xv[k]*t);
                }
                if(maxX - minX < L + EPS && maxY - minY < L + EPS) return true;
            }
        }
    }
    return false;
}