旋转卡壳(求凸包直径)学习笔记 | 题解 P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳
2024-10-20 21:03:39
前言
旋转卡壳(Rotating Calipers)可以在凸包上维护许多有用的信息,最常见的就是凸包直径(平面最远点对)。
注意:本文不介绍所谓的 “人类智慧” 乱搞做法。
算法流程
首先我们需要求出点集的凸包(我个人喜欢 Andrew 算法)。
然后我们考虑选定凸包的一条边所在的直线,比如 \(AB\)。然后找到凸包的所有顶点中离它最远的点,在这个例子中是 \(D\)。然后凸包直径就 可能 是 \(AD\) 或 \(BD\)。
然后我们继续。逆时针选择下一条边 \(AE\),这时我们发现最远点变成了 \(C\),然后尝试用 \(AC,EC\) 更新答案。以此类推。这样我们就找到了凸包直径。
但是这样子时间复杂度是 \(O(n^2)\) 的,应该无法通过。
但是根据以前的经验,似乎最远点也是逆时针旋转的。换句话说,逆时针遍历的点到直线的距离单调。
这也可以用凸包的凸性来解释。我无法给出详细证明,但是大家不妨手动画几个图,就可以感性的理解了。
于是我们就可以用一个漂亮的双指针解决了。
P145 【模板】旋转卡壳 代码
注意本题需要输出凸包直径的平方。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
const double eps=1e-9;
int dcmp(double x){
return (fabs(x)<=eps)?0:(x<0?-1:1);
}
struct Point{
double x,y;
Point(double X=0,double Y=0){x=X,y=Y;}
};
struct Vector{
double x,y;
Vector(double X=0,double Y=0){x=X,y=Y;}
};
inline Vector operator-(Point x,Point y){// 点-点=向量
return Vector(x.x-y.x,x.y-y.y);
}
inline double cross(Vector x,Vector y){ // 向量叉积
return x.x*y.y-x.y*y.x;
}
inline double operator*(Vector x,Vector y){ // 向量叉积
return cross(x,y);
}
inline double len(Vector x){ // 向量模长
return sqrt(x.x*x.x+x.y*x.y);
}
int stk[50005];
bool used[50005];
vector<Point> ConvexHull(Point* poly, int n){ // Andrew算法求凸包
int top=0;
sort(poly+1,poly+n+1,[&](Point x,Point y){
return (x.x==y.x)?(x.y<y.y):(x.x<y.x);
});
stk[++top]=1;
for(int i=2;i<=n;i++){
while(top>1&&dcmp((poly[stk[top]]-poly[stk[top-1]])*(poly[i]-poly[stk[top]]))<=0){
used[stk[top--]]=0;
}
used[i]=1;
stk[++top]=i;
}
int tmp=top;
for(int i=n-1;i;i--){
if(used[i]) continue;
while(top>tmp&&dcmp((poly[stk[top]]-poly[stk[top-1]])*(poly[i]-poly[stk[top]]))<=0){
used[stk[top--]]=0;
}
used[i]=1;
stk[++top]=i;
}
vector<Point> a;
for(int i=1;i<=top;i++){
a.push_back(poly[stk[i]]);
}
return a;
}
struct Line{
Point x;Vector y;
Line(Point X,Vector Y){x=X,y=Y;}
Line(Point X,Point Y){x=X,y=Y-X;}
};
inline double DistanceToLine(Point P,Line x){// 点到直线的距离
Vector v1=x.y, v2=P-x.x;
return fabs(cross(v1,v2))/len(v1);
}
double RoatingCalipers(vector<Point> poly){// 旋转卡壳
if(poly.size()==3) return len(poly[1]-poly[0]);
int cur=0;
double ans=0;
for(int i=0;i<poly.size()-1;i++){
Line line(poly[i],poly[i+1]);
while(DistanceToLine(poly[cur], line) <= DistanceToLine(poly[(cur+1)%poly.size()], line)){
cur=(cur+1)%poly.size();
}
ans=max(ans, max(len(poly[i]-poly[cur]), len(poly[i+1]-poly[cur])));
}
return ans;
}
Point poly[50005];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>poly[i].x>>poly[i].y;
double v=RoatingCalipers(ConvexHull(poly, n));
cout<<(int)(v*v);
return 0;
}
最新文章
- HTML5- Canvas入门(七)
- golang实现冒泡排序
- 使用Windows Form 制作一个简易资源管理器
- iOS开发之AppIcon及LaunchScreen设置
- openwrt的环境搭建、定制和编译
- idea 使用
- 操作Json
- 利用JavaScript 的formdata 进行无刷新上传文件
- 关于Program Size
- Django admin究竟要怎么写才优雅
- Thread部分总结以及小例子
- [原创]K8Cscan插件之FTP弱口令扫描
- docker安装mongodb并备份
- Mac 系统下 mysql 的安装与配置
- 最全面的Spring-Boot-Cache使用与整合
- [No0000143]Win10“卓越性能模式”
- xshell的一些基本操作
- lua --- __newindex
- 『PyTorch』第十一弹_torch.optim优化器
- java中 static,final,transient,volatile关键字的作用
热门文章
- 沁恒CH32V003F4P6 开发板上手报告和Win10环境配置
- UML建模语言、设计原则、设计模式
- 【NGINX】浅尝
- 【题解】CF991C Candies
- Kubernetes核心技术Pod
- SpringBoot+hutool工具-数据库数据导出Excel
- <;七>;理解多态
- Kettle:跨库(SQLServer->;PostgreSQL)同步多张表数据的详细设计过程
- 【十次方微服务后台开发】Day02:加密与JWT鉴权、微服务注册中心、配置中心、熔断器、网关、消息总线、部署与持续集成、容器管理与监控Rancher、influxDB、grafana
- 【Spark】Day03-Spark SQL:DataFrame、DataSet、sql编程与转换、项目实战(区域热门商品)