设为首页 加入收藏

TOP

LA 4728 Square ,旋转卡壳法求多边形的直径
2015-07-20 17:52:16 来源: 作者: 【 】 浏览:1
Tags:4728 Square 旋转 卡壳法 多边形 直径

给出一些正方形,让你求这些正方形顶点之间的最大距离的平方。



//返回点集直径的平方
int diameter2(vector
  
    & points) {
    vector
   
     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; }
   
  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇poj 2079 Triangle,旋转卡壳求点.. 下一篇POJ 1840 Eqs(hash)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: