找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1826|回复: 0

[精彩文萃] 计算几何的凸包模板,c语言实现

[复制链接]

已领礼包: 145个

财富等级: 日进斗金

发表于 2013-12-9 01:01:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×

  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>

  4. typedef struct
  5. {
  6.         double x;
  7.         double y;
  8. }POINT;

  9. POINT result[102];                                                        //保存凸包上的点
  10. POINT a[102];                                                               
  11. int n,top;

  12. double Distance(POINT p1,POINT p2)                        //两点间的距离
  13. {
  14.         return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
  15. }
  16. double Multiply(POINT p1,POINT p2,POINT p3) //叉积
  17. {       
  18.    return ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
  19. }
  20. int Compare(const void *p1,const void *p2)
  21. {
  22.         POINT *p3,*p4;
  23.         double m;
  24.     p3=(POINT *)p1;
  25.     p4=(POINT *)p2;
  26.         m=Multiply(a[0],*p3,*p4) ;
  27.         if(m<0) return 1;
  28.         else if(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4)))
  29.                 return 1;
  30.         else return -1;
  31. }
  32. void Tubao()
  33. {
  34.    int i;
  35.    result[0].x=a[0].x;
  36.    result[0].y=a[0].y;
  37.    result[1].x=a[1].x;
  38.    result[1].y=a[1].y;
  39.    result[2].x=a[2].x;
  40.    result[2].y=a[2].y;
  41.    top=2;
  42.    for(i=3;i<=n;i++)
  43.    {
  44.        while(Multiply(result[top-1],result[top],a)<=0)
  45.                         top--;
  46.        result[top+1].x=a.x;
  47.        result[top+1].y=a.y;
  48.        top++;
  49.    }
  50. }

  51. int main()
  52. {
  53.    int i,p;
  54.    double px,py,len,temp;
  55.    while(scanf("%d",&n)!=EOF,n)
  56.    {
  57.        for(i=0;i<n;i++)
  58.            scanf("%lf%lf",&a.x,&a.y);
  59.        if(n==1)
  60.        {
  61.            printf("0.00\n");
  62.            continue;
  63.        }
  64.        else if(n==2)
  65.        {
  66.            printf("%.2lf\n",Distance(a[0],a[1]));
  67.            continue;
  68.        }
  69.        py=-1;
  70.        for(i=0;i<n;i++)
  71.            {
  72.            if(py==-1 || a.y<py)
  73.            {
  74.                px=a.x;
  75.                py=a.y;
  76.                            p=i;
  77.            }
  78.            else if(a.y==py && a.x<px)
  79.            {
  80.                px=a.x;
  81.                py=a.y;
  82.                            p=i;
  83.            }
  84.            }
  85.            //swap(a[0],a[p])
  86.            temp=a[0].x;
  87.            a[0].x=a[p].x;
  88.            a[p].x=temp;
  89.            temp=a[0].y;
  90.            a[0].y=a[p].y;
  91.            a[p].y=temp;

  92.        qsort(&a[1],n-1,sizeof(double)*2,Compare);
  93.        a[n].x=a[0].x;
  94.        a[n].y=a[0].y;
  95.        Tubao();
  96.        len=0.0;
  97.        for(i=0;i<top;i++)
  98.            len=len+Distance(result,result[i+1]);
  99.        printf("%.2lf\n",len);
  100.    }
  101.    return 0;
  102. }



论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-11-6 03:36 , Processed in 0.366754 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表