首页 > 代码库 > LA 4728 (旋转卡壳) Squares
LA 4728 (旋转卡壳) Squares
题意：
求平面上的最远点对距离的平方。
分析：
对于这个数据量枚举肯定是要超时的。
首先这两个点一定是在凸包上的，所以可以枚举凸包上的点，因为凸包上的点要比原来的点会少很多，可最坏情况下的时间复杂度也是O(n2).
于是就有了旋转卡壳。
可以想象有两条平行直线紧紧地夹住这个凸包，那直线上的点就是对踵点对。对踵点对最多有四对，就是当凸包的两边和两直线重合的情况。
直线的角度不断变化，直线上的对踵点对也会发生变化，当直线旋转过180°后，那么凸包上所有的对踵点对也就全部遍历到了。
代码中还有很详细的注释。
里面是利用比较△(u, u+1, v) 和 △(u, u+1, v+1)的面积大小来寻找对踵点对的。因为是凸多边形，所以面积的比较转化成了两个叉积的比较，最后化简成了一个叉积PuPu+1×PvPv+1。
直接从化简出来的结果来看，如果两个向量的叉乘大于0的话，说明v正在远离直线PuPu+1，如果小于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\n", 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\n", diameter2(p));111 }112 113 return 0;114 }
LA 4728 (旋转卡壳) Squares
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。