计算机几何，极角序，旋转卡壳的板子
最近春招笔试遇到的很眼熟的算法，复习一下~
https://ac.nowcoder.com/acm/contest/66585/D
https://ac.nowcoder.com/acm/contest/66585/E
https://ac.nowcoder.com/acm/contest/66585/G
#include<bits/stdc++.h>
using namespace std;
const int N=2200;
typedef long long db; //全整形直接在这里改
typedef long long ll;
const db EPS=0;
inline int sign(db a){return a<-EPS?-1:a>EPS;} //判断a的符号
inline int cmp(db a,db b){return sign(a-b);}
struct P{
db x,y;
P(){}
P(db _x,db _y):x(_x),y(_y){}
P operator+(P p){return{x+p.x,y+p.y};}
P operator-(P p){return{x-p.x,y-p.y};}
P operator*(db d){return{x*d,y*d};}
P operator/(db d){return{x/d,y/d};}
bool operator<(P p) const{
int c=cmp(x,p.x);
if(c) return c==-1;
return cmp(y,p.y)==-1;
}
bool operator==(P o) const{
return cmp(x,o.x)==0&&cmp(y,o.y)==0;
}
db dot(P p) {return x*p.x+y*p.y;}
//对应相乘的点积 |a|*|b|*cosC
db det(P p) {return x*p.y-y*p.x;}
//交差相乘再相减的叉积 |a|*|b|*sinC,有方向以第一个向量为准 ==平行四边形的面积
db distTo(P p){return (*this-p).abs();} //|x1-x2|+|y1-y2|
db alpha(){return atan2(y,x);} //极角与x轴正半轴的夹角 弧度制
db abs(){return sqrt(abs2());}
db abs2(){ return x*x+y*y;} //到原点的距离平方
P rot90(){return P(-y,x);} //旋转90
P unit(){return *this/abs();} //除于模长
int quad() const{return sign(y)==1||(sign(y)==0&&sign(x)>=0);} //判断是不是位于上半
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
//算(^^p1p2)X(^^p1p3)
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
// crossOp 精度有一点问题 点的范围1e9 eps<=10^(-9)
//算一个上面的符号
bool chkLL(P p1, P p2, P q1,P q2){
db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
return sign(a1+a2)!=0;
}
// 两条直线是不是相交关系
// p1p2,q1q2 是不是恰有一个交点
P isLL(P p1,P p2,P q1,P q2){
db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
return (p1*a2+p2*a1)/(a1*a2);
}
//通过叉积求出面积，然后等比分线段，求p1,p2的交点
bool intersect(db l1,db r1,db l2,db r2){
if(l1>r1) swap(l1,r1);if(l2>r2) swap(l2,r2);
return !( cmp(r1,l2)==-1 || cmp(r2,l1)==-1 );
}
// 判断l1,l2 是否相交 ，可以重，一个点
bool isSS(P p1,P p2,P q1,P q2){
return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&
crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<=0&&crossOp(q1,q2,p1)*
crossOp(q1,q2,p2)<0;
}
//判断是不是严格相交有且仅有一个交点
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<0&&crossOp(q1,q2,p1)*
crossOp(q1,q2,p2)<0;
}
bool isMiddle(db a,db m,db b){
/*
if(a>b) swap(a,b);
return cmp(a,m)<=0&&cmp(m,b)<=0;
*/
return sign(a-m)==0|| sign(b-m)==0|| (a<m!=b<m);
}
// 判断一个点是否在两个点之间
bool isMiddle(P a,P m,P b){
return isMiddle(a.x,m.x,b.x) && isMiddle(a.y,m.y,b.y);
}
//点p是不是在线段p1 p2 上
bool onSeg(P p1,P p2,P q){
return crossOp(p1,p2,q)==0&&isMiddle(p1,q,p2);
}
// 点P严格在p1 p2上m先判断三点共线再判断方向
bool onSeg_strict(P p1,P p2, P q){
return crossOp(p1,p2,q)==0&&sign((q-p1).dot(p1-p2))*sign((q-p2).dot(p1-p2))<0;
}
// q到直线p1,p2的投影 （垂足） !!!p1==p2的情况
P proj(P p1,P p2,P q){
P dir=p2-p1;
return p1+dir*(dir.dot(q-p1)/dir.abs2());
}
// q到直线p1,p2的反射 （垂足） !!!p1==p2的情况
P reflect(P p1,P p2, P q){
return proj(p1,p2,q)*2-q;
}
// 求q到线段p1p2的最小距离
// 先求垂足，判断在不在，不再返回端点
db nearest(P p1,P p2, P q){
if(p1==p2) return p1.distTo(q);
P h=proj(p1,p2,q);
if(isMiddle(p1,h,p2)) return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
// 求两个线段 p1p2线段q1q2的距离
// 找两个点之间的最小值
// 直接找两个端点四个距离求个min
db disSS(P p1,P p2,P q1,P q2){
if(isSS(p1,p2,q1,q2)) return 0.0; //相交返回0
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)),min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
// 极角排序
// 给一些点找这些点按极角大小排序（原点的角度[-PI，PI]）
// atan2() 求度数但是有10-15次方里的误差而且很慢
// 可以用det叉积判断方向 ，一个点在另一个点的方向 这样也不行判段方向会绕一圈
// 先判一个极角是正/负[-PI,0),[0,PI];
// 在同一边再用det判断方向
/*
sort(p,p+n,[&](P &a,P &b){
int qa=a.quad(),qb=b.quad();
if(qa!=qb) return qa<qb;
else return sign(a.det(b))>0;
})
*/
// 算凸多边形的面积
db area(vector<P> ps){
db ret=0;
int sz=ps.size();
for(int i=0;i<sz;i++) ret+=ps[i].det(ps[(i+1)%sz]);
return ret/2.0;
}
// 点是不是在多边形上,2表示在里面,1表示在边界，表示在外面
int contiain(vector<P> ps,P p){
int n=ps.size(),ret=0;
for(int i=0;i<n;i++){
P u=ps[i],v=ps[(i+1)%n];
if(onSeg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y)>0||cmp(p.y,v.y)<=0) continue;
ret^=crossOp(p,u,v)>0;
}
return ret*2;
}
// 考虑点在边上的情况
//算凸包的上下凸壳 ,严格凸包
vector<P> convexHull(vector<P> ps){
int n=ps.size();
if(n<=1) return ps;
sort(ps.begin(),ps.end()); //正常的按x,y排序
vector<P> qs(n*2); //栈 ，共线是不算的
int k=0; //栈顶
for(int i=0;i<n;qs[k++]=ps[i++])
while(k>1&&crossOp(qs[k-2],qs[k-1],ps[i])<=0) --k; //判断是不是顺时针方向 ，是顺时针或着共线就弹掉
for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])
while(k>t&&crossOp(qs[k-2],qs[k-1],ps[i])<=0) --k;
qs.resize(k-1);//保留前k-1个最后一个重的不要
return qs;
}
// 不严格的凸包，共线也算上
vector<P> convexHullNonStrict(vector<P> ps){
//用这个的时候要把点去重一下不然队列里的会有一模一样的点
//共线和下一个的乘积一定是0，要去重
int n=ps.size();
if(n<=1) return ps;
sort(ps.begin(),ps.end());
vector<P> qs(n*2);
int k=0;
for(int i=0;i<n;qs[k++]=ps[i++])
while(k>1&&crossOp(qs[k-2],qs[k-1],ps[i])<0) --k;
for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])
while(k>t&&crossOp(qs[k-2],qs[k-1],ps[i])<0) --k;
qs.resize(k-1);
return qs;
}
// 一条线把凸多边型分开了
vector<P> convexCut(const vector<P> &ps,P q1, P q2){
vector<P> qs;
int n=ps.size();
for(int i=0;i<n;i++){
P p1=ps[i],p2=ps[(i+1)%n];
int d1=crossOp(q1,q2,p1),d2=crossOp(q1,q2,p2);
if(d1>=0) qs.push_back(p1);
if(d1*d2<0) qs.push_back(isLL(p1,p2,q1,q2));
// 如果确定严格相交就直接把端点放进去
}
return qs;
}
// 旋转卡壳 （双指针）
// 有一个点集合，希望找到最远（欧几里得距离）的两个点
// 这两个点一定在凸包上
// 象想有两个平行线在凸多边变行的两端，现在要不停的旋转这个凸多变形
// 我们的全局最远点在某个地方一定会被卡住
// 模拟这个过程即可，双指针卡住
// 考虑到每个平行的位置 对于两个指针的移动看i和j向量的关系 谁在谁的逆时针方向
db convexDiameter(vector<P> ps){
int n=ps.size();
if(n<=1) return 0;
int is=0,js=0;
for(int k=1;k<n;k++) is=ps[k]<ps[is]?k:is,js=ps[js]<ps[k]?k:js; //取最大和最小的
int i=is,j=js;
db ret=(ps[i]-ps[j]).abs2();
do{
if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j])>=0) (++j)%=n;
else (++i)%=n;
ret=max(ret,(ps[i]-ps[j]).abs2());
}while(i!=is||j!=js);
return ret;
}
int main(){
int n;
scanf("%d",&n);
vector<P> a,b;
for(int i=1;i<=n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
a.push_back((P){x,y});
}
b=convexHull(a);
long long t=convexDiameter(b);
printf("%lld\n",t);
return 0;
}
投递高德地图等公司10个岗位 >
阿里云二面89人在聊
查看2道真题和解析