poj 2079 Triangle,旋转卡壳求点集的最大三角形
最大 poj 旋转 三角形 Triangle
2023-09-11 14:20:45 时间
给出一个点集,求顶点在点集中的最大的三角形面积。
我们知道这三角形的三个点肯定在凸包上,我们求出凸包之后不能枚举,由于题目n比較大,枚举的话要O(n^3)的数量级,所以採用旋转卡壳的做法:
首先枚举三角形的第一个顶点i, 初始化第二个顶点j=i+1和第三个顶点k=j+1,对k进行循环,直到找到第一个k使得cross(i,j,k)>cross(i,j,k+1),假设k==i进入下一次循环。
对j,k进行旋转。每次循环之前更新最大值,然后固定一个j,相同找到一个k使得cross(i,j,k)>cross(i,j,k+1)。对j进行++操作,继续进行下一次,知道j==k'(对j,k旋转之前的(k+1)%n)或k==i为止。
double rotating_calipers(vector<Point>& points){ vector<Point> p = ConvexHull(points); int n = p.size(); p.push_back(p[0]); double ans = 0; for(int i=0; i<n; ++i) { int j = (i+1)%n; int k = (j+1)%n; //当Area(P[i], p[j], p[k+1]) <= Area(p[i], p[j], p[k]) 时停止旋转 //即Cross(p[j]-p[i], p[k+1]-p[i]) - Cross(p[j]-p[i], p[k]-p[i]) <= 0 //依据Cross(A,B) - Cross(A,C) = Cross(A,B-C) //化简得Cross(p[j]-p[i], p[k+1] - p[k]) <= 0 while(k!=i && Cross(p[j]-p[i], p[k+1]-p[k]) > 0) k = (k+1) % n; if(k==i) continue; int kk = (k+1) % n; while(j!=kk && k!=i) { ans = max(ans, Cross(p[j]-p[i], p[k]-p[i])); while(k!=i && Cross(p[j]-p[i], p[k+1]-p[k]) > 0) k = (k+1) % n; j = (j+1) % n; } } return ans*0.5; }
相关文章
- C语言程序设计100例之(13):最大子段和
- hdu2830 可交换行的最大子矩阵
- hdu1024 最大m子序列和
- POJ 3228 二分最大流
- POJ 1087 A Plug for UNIX (网络流,最大流)
- 二叉树的最大深度
- 超简单集成 HMS ML Kit 实现最大脸微笑抓拍
- ZOJ 3229 Shoot the Bullet (有源有汇有上下界最大流)
- POJ 3281 Dining (网络流之最大流)
- 如何从管理IT服务提供商获得最大收益
- 剑指offer编程题解法汇总30-连续子数组的最大和
- JDOJ 2982: 最大连续子段和问题
- A10 Fusion很强大 苹果成为英特尔的最大威胁
- 重庆规模最大数据中心启用
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和