首页 > 代码库 > [模板]计算几何(一)

[模板]计算几何(一)

凸包

#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;}

[模板]计算几何(一)