http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=4199

最弱的旋转卡壳。。

/*0.288s*/

#include<bits/stdc++.h>
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<Point> ConvexHull(vector<Point>& p)
{
    /// 预处理,删除重复点
 sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    int m = 0;
    vector<Point> 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<Point>& points)
{
    vector<Point> 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++)
    {
        /// 一条直线贴住边p[u]-p[u+1]
     while(true)
        {
            /// 当Area(p[u], p[u+1], p[v+1]) <= Area(p[u], p[u+1], p[v])时停止旋转
         /// 即Cross(p[u+1]-p[u], p[v+1]-p[u]) - Cross(p[u+1]-p[u], p[v]-p[u]) <= 0
         /// 根据Cross(A,B) - Cross(A,C) = Cross(A,B-C)
         /// 化简得Cross(p[u+1]-p[u], p[v+1]-p[v]) <= 0
         int diff = Cross(p[u + 1] - p[u], p[v + 1] - p[v]);
            if (diff <= 0)
            {
                ans = max(ans, Dist2(p[u], p[v])); /// u和v是对踵点
             if (diff == 0) ans = max(ans, Dist2(p[u], p[v + 1])); /// diff == 0时u和v+1也是对踵点
             break;
            }
            v = (v + 1) % n;
        }
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        vector<Point> points;
        for (int i = 0; i < n; i++)
        {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            points.push_back(Point(x, y));
            points.push_back(Point(x + w, y));
            points.push_back(Point(x, y + w));
            points.push_back(Point(x + w, y + w));
        }
        printf("%d\n", diameter2(points));
    }
    return 0;
}

Comments

comments powered by Disqus