LA 4728 (旋转卡壳) Squares

题意：

求平面上的最远点对距离的平方。

分析：

对于这个数据量枚举肯定是要超时的。

首先这两个点一定是在凸包上的，所以可以枚举凸包上的点，因为凸包上的点要比原来的点会少很多，可最坏情况下的时间复杂度也是O(n²).

于是就有了旋转卡壳。

可以想象有两条平行直线紧紧地夹住这个凸包，那直线上的点就是对踵点对。对踵点对最多有四对，就是当凸包的两边和两直线重合的情况。

直线的角度不断变化，直线上的对踵点对也会发生变化，当直线旋转过180°后，那么凸包上所有的对踵点对也就全部遍历到了。

代码中还有很详细的注释。

里面是利用比较△(u, u+1, v) 和 △(u, u+1, v+1)的面积大小来寻找对踵点对的。因为是凸多边形，所以面积的比较转化成了两个叉积的比较，最后化简成了一个叉积P_uP_u₊₁×P_vP_v+1。

直接从化简出来的结果来看，如果两个向量的叉乘大于0的话，说明v正在远离直线P_uP_u₊₁，如果小于0的话说明正在靠近直线，也很容易理解。

  1 //#define LOCAL
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <vector>
  7 using namespace std;
  8 
  9 struct Point
 10 {
 11     int x, y;
 12     Point(int x=0, int y=0):x(x), y(y){}
 13 };
 14 typedef Point Vector;
 15 
 16 Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); }
 17 Point operator - (Point a, Point b) { return Point(a.x-b.x, a.y-b.y); }
 18 int Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
 19 int Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
 20 
 21 bool operator < (const Point& a, const Point& b)
 22 {
 23     return a.x < b.x || (a.x == b.x && a.y < b.y);
 24 }
 25 
 26 bool operator == (const Point& a, const Point& b)
 27 {
 28     return a.x == b.x && a.y == b.x;
 29 }
 30 
 31 int Dist2(const Point& a, const Point& b)
 32 { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }
 33 
 34 vector<Point> ConvexHull(vector<Point>& p)
 35 {
 36     sort(p.begin(), p.end());
 37     p.erase(unique(p.begin(), p.end()), p.end());
 38     
 39     int n = p.size();
 40     int m = 0;
 41     vector<Point> ch(n+1);
 42     for(int i = 0; i < n; ++i)
 43     {
 44         while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
 45         ch[m++] = p[i];
 46     }
 47     int k = m;
 48     for(int i = n-2; i >= 0; --i)
 49     {
 50         while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
 51         ch[m++] = p[i];
 52     }
 53     if(n > 1) m--;
 54     ch.resize(m);
 55     return ch;
 56 }
 57 
 58 int diameter2(vector<Point>& points)
 59 {
 60     vector<Point> p = ConvexHull(points);
 61     int n = p.size();
 62     //for(int i = 0; i < n; ++i)    printf("%d %d
", p[i].x, p[i].y);
 63     if(n == 1)    return 0;
 64     if(n == 2)  return Dist2(p[0], p[1]);
 65     p.push_back(p[0]);
 66     int ans = 0;
 67     for(int u = 0, v = 1; u < n; ++u)
 68     {// 一条直线贴住边p[u]-p[u+1]
 69         while(true)
 70         {
 71             // 当Area(p[u], p[u+1], p[v+1]) <= Area(p[u], p[u+1], p[v])时停止旋转
 72             //因为两个三角形有一公共边，所以面积大的那个点到直线距离大 
 73             // 即Cross(p[u+1]-p[u], p[v+1]-p[u]) - Cross(p[u+1]-p[u], p[v]-p[u]) <= 0
 74             // 根据Cross(A,B) - Cross(A,C) = Cross(A,B-C)
 75             // 化简得Cross(p[u+1]-p[u], p[v+1]-p[v]) <= 0
 76             int diff = Cross(p[u+1]-p[u], p[v+1]-p[v]);
 77             if(diff <= 0)
 78             {
 79                 ans = max(ans, Dist2(p[u], p[v]));
 80                 if(diff == 0)    ans = max(ans, Dist2(p[u], p[v+1]));
 81                 break;
 82             } 
 83             v = (v+1)%n;
 84         }
 85     }
 86     return ans;
 87 }
 88 
 89 int main(void)
 90 {
 91     #ifdef LOCAL
 92         freopen("4728in.txt", "r", stdin);
 93     #endif
 94     
 95     int T;
 96     scanf("%d", &T);
 97     while(T--)
 98     {
 99         int n, x, y, w;
100         scanf("%d", &n);
101         vector<Point> p;
102         for(int i = 0; i < n; ++i)
103         {
104             scanf("%d%d%d", &x, &y, &w);
105             p.push_back(Point(x, y));
106             p.push_back(Point(x+w, y));
107             p.push_back(Point(x+w, y+w));
108             p.push_back(Point(x, y+w));
109         }
110         printf("%d
", diameter2(p));
111     }
112 
113     return 0;
114 }

代码君