POJ 2187: Beauty Contest - mayoko’s diary

蟻本奴です。

問題

2 次元平面上に N 個の点が与えられる。最も遠い位置関係にある２つの頂点間の距離の二乗の値を求めよ。

解法

蟻本の p233 に書いてあるやつです。ふたつ目の解法でやりました。

ひとつ目の解法では「凸包の頂点数は座標の幅の最大値 M に対して O( $\sqrt{M}$ )」って書いてあるけど全部同一直線上にあったら死なない？と思ってしまいましたが, 凸包では det の値が 0 "以下" だったら頂点を無視し続けるので, 同一直線上の点は無視するからやっぱり大丈夫ですね。

ふたつ目の解法では, 最も遠い点対を凸包を回りながら走査していきます。
p, q が最遠点対であるとすると, p, q は当然 q-p 方向で最も離れている点対です。また, この直線を少しずらしても, やはり p, q は最遠点対です。つまり, 任意の傾きの直線に対して, その最遠点対を見つけることができれば, その距離を取っていくだけで答えを求めることが出来ます。

「任意の傾きの直線」と言っていますが, 実際には凸包の辺に垂直な方向だけを考えれば良いです。なので, ある直線に対する最遠点対 i, j が決まっていれば, その後は i-(i+1) 辺と j-(j+1) 辺のどちらが今考えている直線に近い(回す角度が少ない)かを考えて, 直線を列挙していけば良いです。

最初に基準になる直線が欲しいですが, これはまず最初に x 軸方向に最も遠い点対を用意しておけば大丈夫です。

double eps = 1e-12;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {double d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 凸包
vector<P> convex_hull(vector<P> ps) {
    int n = ps.size();
    sort(ps.begin(), ps.end());
    int k = 0;         // 凸包の頂点数
    vector<P> qs(n*2); // 構築中の凸包
    // 下側凸包の作成
    for (int i = 0; i < n; i++) {
        while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    // 上側凸包の作成
    for (int i = n-2, t = k; i >= 0; i--) {
        while (k > t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}

double dist2(const P& p, const P& q) {
    return (p-q).dot(p-q);
}

int main() {
    int N;
    scanf("%d", &N);
    vector<P> ps(N);
    for (int i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ps[i].x = x, ps[i].y = y;
    }
    vector<P> qs = convex_hull(ps);
    int n = qs.size();
    if (n==2) {
        printf("%.0f\n", dist2(qs[0], qs[1]));
        return 0;
    }
    int i = 0, j = 0;
    for (int k = 0; k < n; k++) {
        if (qs[k] < qs[i]) i = k;
        if (qs[j] < qs[k]) j = k;
    }
    int si = i, sj = j;
    double ans = 0;
    while (i != sj || j != si) {
        ans = max(ans, dist2(qs[i], qs[j]));
        int ni = (i+1)%n, nj = (j+1)%n;
        if ((qs[ni]-qs[i]).det(qs[nj]-qs[j]) < 0) i = ni;
        else j = nj;
    }
    printf("%.0f\n", ans);
    return 0;
}