P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳

Link

Solution

旋转卡壳模板题，注意一些不能形成凸包的情况，并且旋转卡壳函数部分如果直接上jls板子的话会被卡掉第一个点，照着题解改了改过了，目前原因不明。

Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

class Point {
public:
    int x, y;
    Point() = default;
    Point(int xx, int yy) : x(xx), y(yy) {}
    Point operator+(const Point &that) const
    {
        return {x + that.x, y + that.y};
    }
    Point operator-(const Point &that) const
    {
        return {x - that.x, y - that.y};
    }
    Point operator*(int k) const { return {x * k, y * k}; }
    Point operator/(int k) const { return {x / k, y / k}; }
    int operator==(const Point &rhs) const { return x == rhs.x && y == rhs.y; }
    bool operator<(const Point rhs) const
    {
        if (x < rhs.x)
            return true;
        else if (x > rhs.x)
            return false;
        else if (y < rhs.y)
            return true;
        else
            return false;
    }
    int abs2() { return x * x + y * y; }
    int dis(Point k1) { return ((*this) - k1).abs2(); }
};

int cross(Point k1, Point k2) { return k1.x * k2.y - k1.y * k2.x; }

vector<Point> ConvexHull(vector<Point> A, int flag = 1)
{
    int n = A.size();
    vector<Point> ans(n * 2);
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < n; i++) {
        while (now > 0 &&
            cross(ans[now] - ans[now - 1], A[i] - ans[now - 1]) < flag)
            now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for (int i = n - 2; i >= 0; i--) {
        while (now > pre &&
            cross(ans[now] - ans[now - 1], A[i] - ans[now - 1]) < flag)
            now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

int convexDiameter(vector<Point> A)
{
    int j = 2, ans = 0, n = A.size();
    if (n == 2) return A[0].dis(A[1]);
    for (int i = 0; i < n - 1; i++) {
        while (cross(A[i + 1] - A[i], A[j] - A[i]) <
            cross(A[i + 1] - A[i], A[j + 1] - A[i]))
            j = (j + 1) % n;
        ans = max(ans, max(A[i].dis(A[j]), A[i + 1].dis(A[j])));
    }
    return ans;
}

int main()
{
    int n, x, y;
    cin >> n;
    vector<Point> v;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({x, y});
    }
    v = ConvexHull(v);
    int ans = convexDiameter(v);
    printf("%d\n", ans);
    return 0;
}