Beauty Contest

题目链接

[POJ 2187] Beauty Contest

题解

简单题。题意大概是给定一些平面上的点,求出给定点之间的最远点对并输出距离的平方。
旋转卡壳模板题。

代码

#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 50000 + 10;
int n, m;

inline double sqr(const double & a) {
    return a * a;
}

class Point {
public:
    double x, y;
    Point() {};

    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }

    Point operator - (const Point & B) const {
        return Point(x - B.x, y - B.y);
    }

}input[maxn], tb[maxn];

bool cmp(Point p1, Point p2) {
    if (p1.x == p2.x) return p1.y < p2.y;
    return p1.x < p2.x;
}

int sqrdis(Point A, Point B) {
    return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y);
}

double Cross(Point A, Point B) {
    return A.x*B.y - A.y*B.x;
}

void ConvexHull() {
    sort(input, input + n, cmp);
    m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && Cross(tb[m - 1] - tb[m - 2], input[i] - tb[m - 2]) <= 0) m--;
        tb[m++] = input[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        while (m > k && Cross(tb[m - 1] - tb[m - 2], input[i] - tb[m - 2]) <= 0) m--;
        tb[m++] = input[i];
    }
    if (n > 1) m--;
}

int rotating_calipers() {
    int q = 1;
    int ans = 0;
    tb[m] = tb[0];
    for (int i = 0; i < m; i++) {
        while (Cross(tb[i + 1] - tb[i], tb[q + 1] - tb[i]) > Cross(tb[i + 1] - tb[i], tb[q] - tb[i]))
            q = (q + 1) % m;
        ans = max(ans, max(sqrdis(tb[i], tb[q]), sqrdis(tb[i + 1], tb[q + 1])));
    }
    return ans;
}

int main() {
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++)
            cin >> input[i].x >> input[i].y;
        ConvexHull();
        cout << rotating_calipers() << endl;
    }
    return 0;
}

标签: math, geometry

添加新评论