网站开发掌握哪种语言,网站建设与管理的实训,怎么制作一个软件app,wordpress主题编程所谓旋转卡壳#xff0c;就是旋转起来的卡壳 #xff08;逃#xff09;
前言
前置知识#xff1a;凸包 个人感觉很像 two-pointers 算法。 能够在优秀的线性时间复杂度内完成总多求最值#xff08;周长、面积…#xff09;的神奇操作。
解析
给出情境#xff1a; 给… 所谓旋转卡壳就是旋转起来的卡壳 逃
前言
前置知识凸包 个人感觉很像 two-pointers 算法。 能够在优秀的线性时间复杂度内完成总多求最值周长、面积…的神奇操作。
解析
给出情境 给出平面内的 nnn 个点求出所有点中的最远点对。 n≤105n\le 10^5n≤105 首先有一个结论最远点对一定都是点集的凸包的顶点。 较为显然证明可以考虑把凸包内的点延长到凸包一条边上边两边的顶点一定有一个更优。
那么我们就转化成了求凸包上的最远点对这个问题也叫做凸包的直径问题。
给出一些定义 凸包的切线若一条直线过凸包上的一点或一边且整个凸包都在直线的同侧或在线上那么我们就称这条直线为凸包的切线。 对踵点如果经过凸包的两个顶点可以作两条平行的凸包的切线那么就称这两个点是一对对踵点。 不难发现最远点对一定是一对对踵点。 然而个人感觉旋转卡壳这个知识点完全不需要这个概念。
考虑换一个角度每次枚举边然后用到边距离最远的点和边的两端点的距离来更新答案。每次更新答案的点其实都是对踵点 显然最优答案一定会被枚举到。 不难发现如果我们逆时针枚举边最远点的位置也是在逆时针旋转。 那么我们利用类似 two-pointers 的思想就可以线性的求出答案。 问题得以解决。
实现的细节上我比较喜欢的方法是一开始先扫一遍暴力找到指针的起始位置而不是倍长野蛮或者每次移动指针都更新答案玄学。
代码
P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}//basic declare
//#define double long double
const double eps1e-10;
const double piacos(-1.0);//---about vectors (or points)//definition
struct V{double x,y;V():x(0),y(0){}V(double a,double b):x(a),y(b){}
};
V ans[10];//declared for other functions
int tot;
inline void input(V a){scanf(%lf%lf,a.x,a.y);}
void print(const V a,int op1){printf(%.10lf %.10lf,a.x,a.y);putchar(op?10:32);}
//op:endl or space//basic operation
inline V operator (const V a,const V b){return (V){a.xb.x,a.yb.y};}
inline V operator - (const V a,const V b){return (V){a.x-b.x,a.y-b.y};}
inline V operator * (const double x,const V a){return (V){a.x*x,a.y*x};}
inline V operator * (const V a,const double x){return (V){a.x*x,a.y*x};}
inline V operator / (const V a,const double x){return (V){a.x/x,a.y/x};}
inline bool operator (const V a,const V b){return abs(a.x-b.x)epsabs(a.y-b.y)eps;}
inline bool operator ! (const V a,const V b){return !(ab);}
inline double operator * (const V a,const V b){return a.x*b.xa.y*b.y;}
inline double operator ^ (const V a,const V b){return a.x*b.y-a.y*b.x;}
inline double len(const V a){return sqrt(a.x*a.xa.y*a.y);}
inline V mid(const V a,const V b){return (V){(a.xb.x)/2,(a.yb.y)/2};}
inline V chui(const V a){return (V){a.y,-a.x};}//not take direction into account
inline V danwei(const V a){return a/len(a);}
inline double tri_S(const V a,const V b,const V c){return abs((b-a)^(c-a))/2;}//always be non-negative
inline bool operator (const V a,const V b){return a.xb.x-eps||(abs(a.x-b.x)epsa.yb.y-eps);
}
inline double ang(const V a,const V b){return acos((a*b)/len(a)/len(b));}
inline V rotate(const V o,double t){//COUNTER_CLOCKWISEdouble ssin(t),ccos(t);return (V){o.x*c-o.y*s,o.x*so.y*c};
}const int N1e5100;
const int M505;
int n,m;
V p[N],zhan[N];
bool cmp(V a,V b){double d(a-p[1])^(b-p[1]);if(abs(d)eps) return d0;else return len(a-p[1])len(b-p[1]);
}
void graham(V *p,int n){int top0;sort(p1,p1n);sort(p2,p1n,cmp);top0;for(int i1;in;i){while((top1((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))0)) --top;zhan[top]p[i];}memcpy(p,zhan,sizeof(zhan));ntop;return;
}
inline ll calc(const V a,const V b){return (a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y)eps;
}
ll rotate_calipers(V *p,int n){ll res(0);int pl1;for(int i2;in;i){if(((p[2]-p[1])^(p[pl]-p[2]))((p[2]-p[1])^(p[i]-p[2]))) pli;}for(int i1;in;i){while(((p[i1]-p[i])^(p[pl]-p[i1]))((p[i1]-p[i])^(p[pl1]-p[i1]))){pl(pl1)%n;resmax(res,max(calc(p[i],p[pl]),calc(p[i1],p[pl])));}resmax(res,max(calc(p[i],p[pl]),calc(p[i1],p[pl])));}return res;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();for(int i1;in;i) input(p[i]);graham(p,n);p[0]p[n];p[n1]p[1];//for(int i1;in;i) print(p[i]);//putchar(\n);printf(%lld\n,rotate_calipers(p,n));return 0;
}
/*
3 5
0 -2
-5 3
0 -7
*/
