首页 > 代码库 > [模板]计算几何(一)
[模板]计算几何(一)
凸包
#include<set> #include<cmath>#include<ctime>#include<queue>#include<stack>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 100001#define eps 1e-11using namespace std;struct point{ int x,y;double t;}a[N],v[N];int n,u,vn;inline double sqr(int k){ return (double)(k*k);}inline point dec(point x,point y){ return (point){x.x-y.x,x.y-y.y,0.0};}inline int mult(point x,point y){ return x.x*y.y-y.x*x.y;}inline double dis(point x,point y){ return sqrt(sqr(abs(x.x-y.x))+sqr(abs(x.y-y.y)));}inline bool cmp(point x,point y){ if(fabs(x.t-y.t)<eps) return dis(x,a[1])>dis(y,a[1]); return x.t<y.t;} inline void convex(){ u=1; for(int i=2;i<=n;i++) if((a[i].x<a[u].x)||(a[i].x==a[u].x&&a[i].y<a[u].y)) u=i; a[0]=a[u];a[u]=a[1];a[1]=a[0]; for(int i=2;i<=n;i++) a[i].t=atan2(a[i].y-a[1].y,a[i].x-a[1].x); sort(a+2,a+1+n,cmp); v[++vn]=a[1];v[++vn]=a[2];a[++n]=a[1]; for(int i=3;i<=n;i++){ if(fabs(a[i].t-a[i-1].t)<eps) continue; while(vn>1&&mult(dec(a[i],v[vn-1]),dec(v[vn],v[vn-1]))>0) vn--; v[++vn]=a[i]; }}inline void init(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); convex();}int main(){ freopen("convex.in","r",stdin); freopen("convex.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0;}
旋转卡壳
#include<set> #include<cmath>#include<ctime>#include<queue>#include<stack>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 1000001using namespace std;struct point{ int x,y;}a[N];int n;inline point dec(point x,point y){ return (point){x.x-y.x,x.y-y.y};}inline int mult(point x,point y){ return x.x*y.y-x.y*y.x;}inline double sqr(int k){ return (double)(k*k);}inline double dis(point x){ return sqrt(sqr(x.x)+sqr(x.y));}inline int Next(int k){ if(++k>n) return 1; return k;}inline double rorate(){ double di,dia=0.0; if(n==1) return dia; for(int i=1,j=2;i<=n;i++){ while(mult(dec(a[Next(i)],a[i]),dec(a[j],a[i]))<mult(dec(a[Next(i)],a[i]),dec(a[Next(j)],a[i]))) j=Next(j); di=dis(dec(a[i],a[j])); if(di>dia) dia=di; di=dis(dec(a[Next(i)],a[Next(j)])); if(di>dia) dia=di; } return dia;}inline void init(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); printf("%lf\n",rorate());}int main(){ freopen("rorate.in","r",stdin); freopen("rorate.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0;}
[模板]计算几何(一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。