旋转卡壳法求点集的最小覆盖矩形面积以及周长

newer

#include"string.h"  
#include"stdio.h"  
#include"math.h"  
#include"stdlib.h"  
#define M 100009  
#define inf 999999999  
#define eps 1e-10  
typedef struct node  
{  
    double x,y,cos,dis;  
}E;  
E p[M],q[M],pp[M];  
double max(double a,double b)  
{  
    return a>b?a:b;  
}  
double min(double a,double b)  
{  
    return a<b?a:b;  
}  
int cmp(const void *a,const void *b)  
{  
    if(fabs((*(struct node*)a).cos-(*(struct node*)b).cos)<eps)  
        return (*(struct node*)a).dis>(*(struct node*)b).dis?1:-1;  
    else  
        return (*(struct node*)b).cos>(*(struct node*)a).cos?1:-1;  
}  
double angle(node p1,node p2)  
{  
    double x1=p2.x-p1.x;  
    double y1=p2.y-p1.y;  
    double x2=1;  
    double y2=0;  
    return (x1*x2+y1*y2)/sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));  
}  
double pow(double x)  
{  
    return x*x;  
}  
double Len(node p1,node p2)  
{  
    return pow(p2.x-p1.x)+pow(p2.y-p1.y);  
}  
double cross(node p0,node p1,node p2)//叉积  
{  
    double x1=p1.x-p0.x;  
    double y1=p1.y-p0.y;  
    double x2=p2.x-p0.x;  
    double y2=p2.y-p0.y;  
    return x1*y2-x2*y1;  
}  
double dot(node p0,node p1,node p2)//点积  
{  
    double x1=p1.x-p0.x;  
    double y1=p1.y-p0.y;  
    double x2=p2.x-p1.x;  
    double y2=p2.y-p1.y;  
    return x1*x2+y1*y2;  
}  
int main()  
{  
    int n,i,j;  
    while(scanf("%d",&n),n)  
    {  
        int tep;  
        E start;  
        start.x=start.y=inf;  
        for(i=0;i<n;i++)  
        {  
            scanf("%lf%lf",&p[i].x,&p[i].y);  
            if(p[i].y<start.y)  
            {  
                start=p[i];  
                tep=i;  
            }  
            else if(fabs(p[i].y-start.y)<eps)  
            {  
                if(p[i].x<start.x)  
                {  
                    start=p[i];  
                    tep=i;  
                }  
            }  
        }  
        p[tep].dis=0;  
        p[tep].cos=1.0;  
        for(i=0;i<n;i++)  
        {  
            if(i!=tep)  
            {  
                if(fabs(p[i].x-start.x)<eps&&fabs(p[i].y-start.y)<eps)  
                {  
                    p[i].dis=0;  
                    p[i].cos=1.0;  
                }  
                else  
                {  
                    p[i].cos=angle(start,p[i]);  
                    p[i].dis=Len(start,p[i]);  
                }  
            }  
        }  
        qsort(p,n,sizeof(p[0]),cmp);//按极角进行快排  
        int tt=0;  
        for(i=0;i<n;i++)//除重点  
        {  
            if(fabs(p[i].dis-p[(i+1)%n].dis)>eps||fabs(p[i].cos-p[(i+1)%n].cos)>eps)  
                pp[tt++]=p[i];  
        }  
        if(tt==0)  
        {  
            printf("0.00 0.00\n");  
            continue;  
        }  
        if(tt==2)  
        {  
            printf("%.2lf %.2lf\n",0.0,2*sqrt(Len(pp[0],pp[1])));  
            continue;  
        }  
        q[0]=pp[tt-1];  
        q[1]=pp[0];  
        q[2]=pp[1];  
        int cnt=2;  
        for(i=2;i<tt;i++)  
        {  
            while(cross(q[cnt-1],q[cnt],pp[i])<0)  
            {  
                cnt--;  
            }  
            q[++cnt]=pp[i];  
        }//求凸包  
        j=1;  
        int k1,k2;  
        k1=k2=1;  
        double S=inf,C=inf;  
        for(i=0;i<cnt;i++)  
        {  
            double w=sqrt(Len(q[i],q[(i+1)%cnt]));  
            while(cross(q[i],q[(i+1)%cnt],q[(j+1)%cnt])>cross(q[i],q[(i+1)%cnt],q[j%cnt]))  
            {  
                j++;  
            }  
            double high=cross(q[i],q[(i+1)%cnt],q[j%cnt])/w;  
            while(dot(q[i],q[(i+1)%cnt],q[(k1+1)%cnt])>dot(q[i],q[(i+1)%cnt],q[(k1%cnt)]))  
            {  
                k1++;  
            }  
            if(i==0)  
                k2=k1;  
            while(dot(q[i],q[(i+1)%cnt],q[(k2+1)%cnt])<=dot(q[i],q[(i+1)%cnt],q[(k2%cnt)]))  
            {  
                k2++;  
            }  
            double wide=(dot(q[i],q[(i+1)%cnt],q[(k1%cnt)])-dot(q[i],q[(i+1)%cnt],q[(k2%cnt)]))/w;  
            //printf("%.3lf %.3lf %.3lf\n",high,wide,(high+wide)*2);  
            S=min(S,high*wide);  
            C=min(C,(high+wide)*2);  
  
        }  
        printf("%.2lf %.2lf\n",S,C);  
    }  
    return 0;  
}  

cable2004

有没有lisp版？

marting

cable2004 发表于 2017-1-21 19:57

应该很容易改成LISP的。

剖开这个代码，说下方法，先求出凸包，然后做个多边形POLYLINE，然后循环每个边，求每个边方向上的最大包围盒，找出这些包围盒的面积最小的。