PKU 2926: Requirements

マンハッタン距離使う問題が解けていないので、類題を探してやってみました.japljさんの記事を参考にしました.

5次元でのマンハッタン距離の最遠点対を求める問題.
普通にやると, O(点の数^2)になる所を工夫します.

5次元で考えるのは面倒なので, 2次元で考えてみます.
当然なようですが,
|x1-x2|+|y1-y2| = max{x1 + y1 - (x2 + y2), x1 - y1 - (x2 - y2), -x1 + y1 - (-x2 + y2), -x1 - y1 - (-x2 - y2)}

と表されます. すなわち, N個の点のなかの最遠の点対(xa, ya), (xb, yb)は
xa + ya ≧ xi + yi (1 ≦ i ≦ N) かつ xb + yb ≦ xi + yi
xa - ya ≧ xi - yi かつ xb - yb ≦ xi - yi
- xa + ya ≧ - xi + yi かつ -xb + yb ≦ -xi + yi
-xa - ya ≧ -xi - yi かつ -xb - yb ≦ -xi - yi

のいずれかを満たしていることとなります. x + yが最大になる点などはO(N)で見つけられるので, O(N)で最遠点対を決定することが出来ます.
k次元のマンハッタン距離でも同じ議論ができ, +-の富豪を考慮して, O(N * 2^k)で最遠点対を求めることが出来ます.

#include <stdio.h>

int main(void)
{
    static double p[100000][5];
    double min[32], max[32];
    int n;
    int i, j, k;
    double dat;
    double ans;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++){
        for (j = 0; j < 5; j++){
            scanf("%lf", &p[i][j]);
        }
    }
    
    ans = 0;
    for (i = 0; i < 1 << 5; i++){
        for (j = 0; j < n; j++){
            dat = 0;
            for (k = 0; k < 5; k++){
                if ((i >> k) & 1){
                    dat += p[j][k];
                }
                else {
                    dat -= p[j][k];
                }
            }
            if (j == 0){
                min[i] = max[i] = dat;
            }
            else {
                if (dat < min[i]){
                    min[i] = dat;
                }
                if (dat > max[i]){
                    max[i] = dat;
                }
            }
        }
        ans = ans > max[i] - min[i] ? ans : max[i] - min[i];
    }
    
    printf("%.2lf\n", ans);
    
    return (0);
}