poj 2187 Beauty Contest , 旋轉卡殼求凸包的直徑的平方

poj 2187 Beauty Contest , 旋轉卡殼求凸包的直徑的平方

旋轉卡殼求凸包的直徑的平方

板子題

#include
#include
#include
#include
using namespace std;

struct Point {
    int x, y;
    Point(int x=0, int y=0):x(x),y(y) { }
};

typedef Point Vector;

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

int Cross(const Vector& A, const Vector& B) {
    return A.x*B.y - A.y*B.x;
}

int Dot(const Vector& A, const Vector& B) {
    return A.x*B.x + A.y*B.y;
}

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

bool operator < (const Point& p1, const Point& p2) {
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

bool operator == (const Point& p1, const Point& p2) {
    return p1.x == p2.x && p1.y == p2.y;
}

// 點集凸包
// 如果不希望在凸包的邊上有輸入點，把兩個 <= 改成 <
// 注意：輸入點集會被修改
vector ConvexHull(vector& p) {
    // 預處理，刪除重復點
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    int n = p.size();
    int m = 0;
    vector ch(n+1);
    for(int i = 0; i < n; i++) {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i--) {
        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    ch.resize(m);
    return ch;
}

//返回點集直徑的平方
int diameter2(vector & points) {
    vector p = ConvexHull(points);
    int n = p.size();
    if(n==1) return 0;
    if(n==2) return Dist2(p[0], p[1]);
    p.push_back(p[0]);
    int ans = 0;
    for(int u = 0, v = 1; u < n; ++u) {
        for(;;) {
            int diff = Cross(p[u+1]-p[u], p[v+1]-p[v]);
            if(diff<=0) {
                ans = max(ans, Dist2(p[u], p[v]));
                if(diff==0) ans = max(ans, Dist2(p[u], p[v+1]));
                break;
            }
            v = (v+1) % n;
        }
    }
    return ans;
}
int main() {
    int n;
    scanf("%d", &n);
    vector P;
    for(int i=0; i