首页 > 代码库 > LA 4728 Square ,旋转卡壳法求多边形的直径
LA 4728 Square ,旋转卡壳法求多边形的直径
给出一些正方形,让你求这些正方形顶点之间的最大距离的平方。
//返回点集直径的平方 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) { 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。