注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj1696 Space Ant 卷包裹法 向量叉积比较  

2011-02-25 21:46:36|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
要求将点集顺时针连接,且线不交叉,输出最多能连的点数,并输出路径。
由于最近一直在看凸包问题,所以读完题,首先想到Graham法,不过Graham法用得比较麻烦。后来上网看了下解题报告,原来卷包裹法才是正解,于是用卷包裹法又解了一遍。这里把这两种方法都写一写吧。
Graham法:递归求每层凸包,每层凸包的最后一点A,要去找下一层凸包与A向左转最小角的点做为下一点B,(因为题目要求逆时针,并不交叉)即下一个凸包起点。想想其实和卷包裹法思想差不多;
卷包裹法:以最左下方的点为起点A,找其余与A向左转最小角的点做为下一点B,然后用同样的方法再去找B的下一个点,直到找完所有点。是不是要比上面的Graham法简便多了。
1、Graham法
Source Code 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int num,top;
struct node
{
   int x;
   int y;
   int z;
}a[55],b[50],c[55]; //a顶点输入,之后还用来记录未进入路径并不再凸包上的点,b当栈使用记录凸包顶点,c记录路径。
int cmp(const void *c,const void *d)
{
   int ans;
   struct node *p1=(node *)c;
   struct node *p2=(node *)d;
   ans=(p1->x-a[0].x)*(p2->y-a[0].y)-(p2->x-a[0].x)*(p1->y-a[0].y);     
   if (ans>0) return -1;
   else if (ans<0) return 1;
   else
   {
     if (abs(a[0].x-p1->x)<abs(a[0].x-p2->x)) return -1;
     else return 1;
   }
}
int find( int p2,int p1,int p0)   //叉乘判断转向
{
    return (b[p1].x-b[p0].x)*(a[p2].y-b[p0].y)-(a[p2].x-b[p0].x)*(b[p1].y-b[p0].y);
}
int find2( int p2,int p1,int p0)  
{
    return (b[p1].x-c[p0].x)*(a[p2].y-c[p0].y)-(a[p2].x-c[p0].x)*(b[p1].y-c[p0].y);
}
void ok(int n)
{
     int i,minx=50005,miny=50005;
     for(i=0;i<n;i++)
     if (a[i].y<miny || (miny==a[i].y && a[i].x<minx))       //记录y值最小的点 有多个时 选x最小的
        {
            miny=a[i].y;minx=a[i].x;num=i;
        }
     a[n]=a[num];       //将y最小的点当成极坐标的原点
     a[num]=a[0];
     a[0]=a[n];
}
void Graham(int n)
{
     int d,to=1,i,j;
     ok(n);
     qsort(a+1,n-1,sizeof(a[0]),cmp);
     b[0]=a[0];
     b[1]=a[1];
     j=0;
     for (i=2;i<n;i++)
     {
         while (to!=0&&find(i,to,to-1)<0)     //如果向右转,就把栈顶退一个,直到新加入的点是向左转为止,包括等零
         {
               a[j]=b[to];
               j++;
               to--;
         }
         b[++to]=a[i];                   //进栈
     }
     a[n]=b[0];
     d=0;
    if(top!=-1)
    for(i=1;i<=to;i++)
       if(find2(n,i,top)>0||(find2(n,i,top)==0&&(pow(b[i].x-c[top].x,2)+pow(b[i].y-c[top].y,2)<pow(a[n].x-c[top].x,2)+pow(a[n].y-c[top].y,2))))
       {
         a[n]=b[i];
         d=i;
       }
     for(i=d;i<=to;i++)
     c[++top]=b[i];
     for(i=0;i<d;i++)
     c[++top]=b[i];
     if(j==1)
     c[++top]=a[0];
     else if(j>1) Graham(j);
}
main ()
{
         // freopen ("1.txt","r",stdin);
    int n,i,t;
    scanf("%d",&t);
    while(t--)
    {
    top=-1;
    scanf("%d",&n);
    for (i=0;i<n;i++)
        scanf("%d%d%d",&a[i].z,&a[i].x,&a[i].y);
     ok(n);
     qsort(a+1,n-1,sizeof(a[0]),cmp);  //按极角由小到大(逆时针)排序,有多个极角相同的,按离原点近的排
     Graham(n);
     printf("%d",top+1);
     for(i=0;i<=top;i++)
     {
       printf(" %d",c[i].z);
     }
     printf("\n");
     }
     system("pause");
     return 0;
}
2、卷包裹法
Source Code 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int n,num;
struct node
{
   int x;
   int y;
   int z;
   int flag;
}a[55],b[50]; //b当栈使用
int find( int p2,int p1,int p0)   //叉乘判断转向
{
    return (a[p1].x-b[p0].x)*(a[p2].y-b[p0].y)-(a[p2].x-b[p0].x)*(a[p1].y-b[p0].y);
}
bool dis(int i,int num,int ans)
{
    return pow(a[i].x-b[ans].x,2)+pow(a[i].y-b[ans].y,2)<pow(a[num].x-b[ans].x,2)+pow(a[num].y-b[ans].y,2);
}
main ()
{
         // freopen ("1.txt","r",stdin);
    int ans,i,t,miny,minx;
    scanf("%d",&t);
    while(t--)
    {
    miny=5000,minx=5000;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%d%d%d",&a[i].z,&a[i].x,&a[i].y);
        a[i].flag=1;
         if (a[i].y<miny || (miny==a[i].y && a[i].x<minx))       //记录y值最小的点 有多个时 选x最小的
        {
            miny=a[i].y;minx=a[i].x;num=i;
        }
    }
    b[0]=a[num];
    ans=0;
    a[num].flag=0;
    while(ans!=n-1)
    {
       for(i=0;i<n;i++)
         if(a[i].flag)
         {
           num=i;
           break;
         }
       for(i=0;i<n;i++)
         if(i!=num&&a[i].flag&&(find(i,num,ans)<0||(find(i,num,ans)==0&&dis(i,num,ans))))
         num=i;
       b[++ans]=a[num];
       a[num].flag=0;
    }
    printf("%d",ans+1);
    for(i=0;i<=ans;i++)
       printf(" %d",b[i].z);
    printf("\n");
    }
    system("pause");
    return 0;
}
  评论这张
 
阅读(446)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018