[关闭]
@Junlier 2018-09-18T11:38:29.000000Z 字数 1672 阅读 2326

凸包模板——Graham扫描法

数学方法——计算几何

First

题目:洛谷P2742[模板]二维凸包/[USACO5.1]圈奶牛Fencing the Cows
yyb的讲解:https://www.cnblogs.com/cjyyb/p/7260523.html

模板

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define lst long long
  13. #define ldb long double
  14. #define N 50050
  15. using namespace std;
  16. const int Inf=1e9;
  17. int read()
  18. {
  19. int s=0,m=0;char ch=getchar();
  20. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  21. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  22. return m?-s:s;
  23. }
  24. int n,top;
  25. struct NODE{ldb x,y;}ljl[N],tb[N];
  26. //tb[]用来储存在凸包上的点(数组模拟栈来维护)
  27. //极角排序的cmp
  28. bool cmp(const NODE &a,const NODE &b)
  29. {
  30. ldb A=atan2((a.y-ljl[1].y),(a.x-ljl[1].x));//就是那个角度(极角)
  31. ldb B=atan2((b.y-ljl[1].y),(b.x-ljl[1].x));
  32. if(A==B)return a.x<b.x;
  33. return A<B;
  34. }
  35. /************************
  36. 计算叉积(向量之间)(向量用坐标法表示)
  37. A×B>0 则说明B在A的左上方
  38. A×B<0 则说明B在A的右下方
  39. ************************/
  40. ldb Cross(NODE a,NODE b,NODE c)
  41. {
  42. return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  43. }
  44. void Get_tb()
  45. {
  46. NODE hh=(NODE){Inf,Inf};int kk=0;
  47. for(int i=1;i<=n;++i)
  48. if((ljl[i].y<hh.y)||(ljl[i].y==hh.y&&ljl[i].x<hh.x))
  49. hh=ljl[i],kk=i;
  50. swap(ljl[1],ljl[kk]);//先找一个凸包的“起点”放在第一个
  51. sort(&ljl[2],&ljl[n+1],cmp);//极角排序
  52. tb[0]=ljl[1],tb[top=1]=ljl[2];
  53. for(int i=3;i<=n;++i)//按极角排序的顺序一个一个判断
  54. {
  55. while(top&&Cross(tb[top-1],ljl[i],tb[top])>=0)top--;
  56. //如果凸包还存在 且 叉积>=0(新加的这个向量在从前向量的左上方)就要一直弹
  57. tb[++top]=ljl[i];
  58. }
  59. }
  60. ldb Dist(NODE a,NODE b)
  61. {//两点之间的距离
  62. return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  63. }
  64. void Get_zc()
  65. {
  66. ldb C=0;
  67. for(int i=1;i<=top;++i)
  68. C+=Dist(tb[i-1],tb[i]);//凸包上两点的距离
  69. if(top>1)C+=Dist(tb[top],tb[0]);//记得首尾相接
  70. printf("%.2Lf\n",C);
  71. }
  72. int main()
  73. {
  74. n=read();
  75. for(int i=1;i<=n;++i)
  76. scanf("%Lf%Lf",&ljl[i].x,&ljl[i].y);
  77. Get_tb(),Get_zc();
  78. return 0;
  79. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注