算法模板——计算几何2（二维凸包——Andrew算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法模板——计算几何2（二维凸包——Andrew算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2236字，纯文字阅读大概需要4分钟。
内容图文
实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298）
很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反过来求另一半的凸包
我以前正是因为总抱着想一步到位的想法，所以每次都跪得很惨（HansBug：事实上这次是我这辈子第一次A掉凸包题）
然后别的没了，就是凸包的基本思想
（顺便输出凸包周长C和面积S，好评如潮哦）
1
type arr=array[0..100005] of longint;
2var 3 i,j,k,l,m,n,m1,m2:longint;
4 a:array[0..100005,1..2] of longint;
5 b,c,d:arr;ans,are:extended;
6procedure swap(var x,y:longint);
7var z:longint;
8begin 9 z:=x;x:=y;y:=z;
10end;
11procedure sort(l,r:longint);
12var i,j,x,y:longint;
13begin14 i:=l;j:=r;x:=a[(l+r) div2,1];y:=a[(l+r) div2,2];
15repeat16while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
17while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
18if i<=j then19begin20 swap(a[i,1],a[j,1]);
21 swap(a[i,2],a[j,2]);
22 inc(i);dec(j);
23end;
24until i>j;
25if i<r then sort(i,r);
26if l<j then sort(l,j);
27end;
28function right(x1,y1,x2,y2:longint):boolean;
29begin30 exit((x1*y2)>(x2*y1));
31end;
32function trip(x1,y1,x2,y2,x3,y3:longint):boolean;
33begin34 exit(right(x2-x1,y2-y1,x3-x2,y3-y2));
35end;
36function check(x,y,z:longint):boolean;
37begin38 exit(trip(a[x,1],a[x,2],a[y,1],a[y,2],a[z,1],a[z,2]));
39end;
40procedure doit(var b:arr;var m:longint);
41begin42 b[1]:=d[1];b[2]:=d[2];j:=2;
43for i:=3to n do44begin45while (j>1) andnot(check(b[j-1],b[j],d[i])) do dec(j);
46 inc(j);b[j]:=d[i];
47end;
48 m:=j;
49end;
50begin51 readln(n);
52for i:=1to n do readln(a[i,1],a[i,2]);
53 sort(1,n);j:=1;
54for i:=2to n do //去重
55begin56if (a[i,1]<>a[j,1]) or (a[i,2]<>a[j,2]) then57begin58 inc(j);
59 a[j,1]:=a[i,1];a[j,2]:=a[i,2];
60end;
61end;
62 n:=j;
63 //求凸包
64for i:=1to n do d[i]:=i;doit(b,m1);
65for i:=1to n do d[i]:=n+1-i;doit(c,m2);
66 //两个半边整合
67for i:=1to m1 do d[i]:=b[i];
68for i:=2to m2 do d[i+m1-1]:=c[i];
69 //开始计算周长+面积
70 m:=m1+m2-2;ans:=0;are:=0;
71for i:=1to m do ans:=ans+sqrt(sqr(a[d[i],1]-a[d[i+1],1])+sqr(a[d[i],2]-a[d[i+1],2])); //周长
72for i:=1to m do are:=are+a[d[i],1]*a[d[i+1],2]-a[d[i],2]*a[d[i+1],1]; //面积
73 are:=abs(are)/2;
74 writeln(‘Convex Hull:‘);
75for i:=1to m do writeln(a[d[i],1],‘‘,a[d[i],2]);
76 writeln(‘C = ‘,ans:0:1);
77 writeln(‘S = ‘,are:0:1);
78 readln;
79end.
原文：http://www.cnblogs.com/HansBug/p/4442921.html
内容总结
以上是互联网集市为您收集整理的算法模板——计算几何2（二维凸包——Andrew算法）全部内容，希望文章能够帮你解决算法模板——计算几何2（二维凸包——Andrew算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。