计算几何的凸包模板，c语言实现

XDSoft

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #include <stdlib.h>
   
4. 
   
5. typedef struct
   
6. {
   
7.         double x;
   
8.         double y;
   
9. }POINT;
   
10. 
    
11. POINT result[102];                                                        //保存凸包上的点
    
12. POINT a[102];                                                               
    
13. int n,top;
    
14. 
    
15. double Distance(POINT p1,POINT p2)                        //两点间的距离
    
16. {
    
17.         return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
    
18. }
    
19. double Multiply(POINT p1,POINT p2,POINT p3) //叉积
    
20. {       
    
21.    return ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
    
22. }
    
23. int Compare(const void *p1,const void *p2)
    
24. {
    
25.         POINT *p3,*p4;
    
26.         double m;
    
27.     p3=(POINT *)p1;
    
28.     p4=(POINT *)p2;
    
29.         m=Multiply(a[0],*p3,*p4) ;
    
30.         if(m<0) return 1;
    
31.         else if(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4)))
    
32.                 return 1;
    
33.         else return -1;
    
34. }
    
35. void Tubao()
    
36. {
    
37.    int i;
    
38.    result[0].x=a[0].x;
    
39.    result[0].y=a[0].y;
    
40.    result[1].x=a[1].x;
    
41.    result[1].y=a[1].y;
    
42.    result[2].x=a[2].x;
    
43.    result[2].y=a[2].y;
    
44.    top=2;
    
45.    for(i=3;i<=n;i++)
    
46.    {
    
47.        while(Multiply(result[top-1],result[top],a)<=0)
    
48.                         top--;
    
49.        result[top+1].x=a.x;
    
50.        result[top+1].y=a.y;
    
51.        top++;
    
52.    }
    
53. }
    
54. 
    
55. int main()
    
56. {
    
57.    int i,p;
    
58.    double px,py,len,temp;
    
59.    while(scanf("%d",&n)!=EOF,n)
    
60.    {
    
61.        for(i=0;i<n;i++)
    
62.            scanf("%lf%lf",&a.x,&a.y);
    
63.        if(n==1)
    
64.        {
    
65.            printf("0.00\n");
    
66.            continue;
    
67.        }
    
68.        else if(n==2)
    
69.        {
    
70.            printf("%.2lf\n",Distance(a[0],a[1]));
    
71.            continue;
    
72.        }
    
73.        py=-1;
    
74.        for(i=0;i<n;i++)
    
75.            {
    
76.            if(py==-1 || a.y<py)
    
77.            {
    
78.                px=a.x;
    
79.                py=a.y;
    
80.                            p=i;
    
81.            }
    
82.            else if(a.y==py && a.x<px)
    
83.            {
    
84.                px=a.x;
    
85.                py=a.y;
    
86.                            p=i;
    
87.            }
    
88.            }
    
89.            //swap(a[0],a[p])
    
90.            temp=a[0].x;
    
91.            a[0].x=a[p].x;
    
92.            a[p].x=temp;
    
93.            temp=a[0].y;
    
94.            a[0].y=a[p].y;
    
95.            a[p].y=temp;
    
96. 
    
97.        qsort(&a[1],n-1,sizeof(double)*2,Compare);
    
98.        a[n].x=a[0].x;
    
99.        a[n].y=a[0].y;
    
100.        Tubao();
     
101.        len=0.0;
     
102.        for(i=0;i<top;i++)
     
103.            len=len+Distance(result,result[i+1]);
     
104.        printf("%.2lf\n",len);
     
105.    }
     
106.    return 0;
     
107. }
     

#include <stdio.h><br /> #include <math.h><br /> #include <stdlib.h><br /> <br /> typedef struct<br /> {<br />         double x;<br />         double y;<br /> }POINT;<br /> <br /> POINT result[102];                                                        //保存凸包上的点<br /> POINT a[102];                                                                <br /> int n,top;<br /> <br /> double Distance(POINT p1,POINT p2)                        //两点间的距离<br /> {<br />         return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));<br /> }<br /> double Multiply(POINT p1,POINT p2,POINT p3) //叉积<br /> {        <br />    return ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x)); <br /> }<br /> int Compare(const void *p1,const void *p2)<br /> {<br />         POINT *p3,*p4;<br />         double m;<br />     p3=(POINT *)p1; <br />     p4=(POINT *)p2; <br />         m=Multiply(a[0],*p3,*p4) ;<br />         if(m<0) return 1;<br />         else if(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4)))<br />                 return 1;<br />         else return -1;<br /> }<br /> void Tubao()<br /> {<br />    int i;<br />    result[0].x=a[0].x;<br />    result[0].y=a[0].y;<br />    result[1].x=a[1].x;<br />    result[1].y=a[1].y;<br />    result[2].x=a[2].x;<br />    result[2].y=a[2].y;<br />    top=2;<br />    for(i=3;i<=n;i++)<br />    {<br />        while(Multiply(result[top-1],result[top],a<i>)<=0)<br />                         top--;<br />        result[top+1].x=a<i>.x;<br />        result[top+1].y=a<i>.y;<br />        top++;<br />    }<br /> }<br /> <br /> int main()<br /> {<br />    int i,p;<br />    double px,py,len,temp;<br />    while(scanf("%d",&n)!=EOF,n)<br />    {<br />        for(i=0;i<n;i++)<br />            scanf("%lf%lf",&a<i>.x,&a<i>.y);<br />        if(n==1)<br />        {<br />            printf("0.00\n");<br />            continue;<br />        }<br />        else if(n==2)<br />        {<br />            printf("%.2lf\n",Distance(a[0],a[1]));<br />            continue;<br />        }<br />        py=-1;<br />        for(i=0;i<n;i++)<br />            {<br />            if(py==-1 || a<i>.y<py)<br />            {<br />                px=a<i>.x;<br />                py=a<i>.y;<br />                            p=i;<br />            }<br />            else if(a<i>.y==py && a<i>.x<px)<br />            {<br />                px=a<i>.x;<br />                py=a<i>.y;<br />                            p=i;<br />            }<br />            }<br />            //swap(a[0],a[p])<br />            temp=a[0].x;<br />            a[0].x=a[p].x;<br />            a[p].x=temp;<br />            temp=a[0].y;<br />            a[0].y=a[p].y;<br />            a[p].y=temp;<br /> <br />        qsort(&a[1],n-1,sizeof(double)*2,Compare);<br />        a[n].x=a[0].x;<br />        a[n].y=a[0].y;<br />        Tubao();<br />        len=0.0;<br />        for(i=0;i<top;i++)<br />            len=len+Distance(result<i>,result[i+1]);<br />        printf("%.2lf\n",len);<br />    }<br />    return 0;<br /> }<br />