凸包 Graham扫描法 TOJ 1255 Surround the Trees&&TOJ 3100 女生寝室的围墙

港控/mmm° 2022-06-04 02:49 170阅读 0赞

凸包算法有很多种... 我就学了一种Graham扫描法..以不变应万变...

![20171202143352740][]

1.把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。  
2.把所有点的坐标平移一下，使 P0 作为原点，如上图。  
3.计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。  
（以上是准备步骤，以下开始求凸包）  
以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：  
4.连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。  
5.如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。  
6.当前点是凸包上的点，把它压入栈，执行步骤7。  
7.检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。

最后，栈中的元素就是凸包上的点了。 （好想放个动图哦emmm可是放不上来）

大概不会动的图片就是这样描述的了...

![20171202143636420][]

TOJ 1255 Surround the Trees

<table> 
 <tbody> 
 <tr> 
 <td> <h2 style="margin-left:0px;">1255: Surround the Trees&nbsp;<img alt="分享至QQ空间" src="http://acm.tzc.edu.cn/acmhome/forum/images/ico_qzone.gif"></h2> 时间限制(普通/Java):1000MS/10000MS &nbsp; &nbsp; 内存限制:65536KByte 总提交: 572 &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; 测试通过:203 描述 &nbsp; There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him? The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line. &nbsp; <img alt="" src="http://acm.tzc.edu.cn/acmhome/judge/images/1255.gif"> &nbsp; There are no more than 100 trees. &nbsp; &nbsp; 输入 &nbsp; The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank. Zero at line for number of trees terminates the input for your program. &nbsp; 输出 &nbsp; The minimal length of the rope. The precision should be 10^-2. </td> 
 </tr> 
 </tbody> 
</table>

![20171202143748787][]

#include<stdio.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 struct point
 {
 double x,y;
 }f[1050],stack1[1050];
 double jl(point p1,point p2)
 {//距离
 return (double)sqrt(1.0*(p1.x-p2.x)*(p1.x-p2.x)+1.0*(p1.y-p2.y)*(p1.y-p2.y));
 }
 double cj(point p0,point p1,point p2)
 {//差积 
 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 }
 bool cmp(point u,point w)
 {//排序
 double x=cj(f[0],u,w);
 if(x>0)return true;
 else if(x<0)return false;
 double len1=jl(f[0],u);
 double len2=jl(f[0],w);
 return len1<len2;
 }
 int main()
 {
 int n,i,j,top;
 while(scanf("%d",&n))
 { 	
 if(n==0)break;
 for(i=0;i<n;i++)
 scanf("%lf%lf",&f[i].x,&f[i].y);
 if(n==1)
 {
 printf("0.00\n");
 continue;
 }
 else if(n==2)
 {
 printf("%.2lf\n",2*jl(f[0],f[1]));
 continue;
 }
 else
 {
 top=2;
 for(i=1;i<n;i++)
 {
 if(f[i].y<f[0].y||(f[i].y==f[0].y&&f[i].x<f[0].x))
 swap(f[0],f[i]);
 }
 sort(f+1,f+n,cmp);
 f[n]=f[0];
 	for(i=0;i<=2;i++)
 	stack1[i]=f[i];
 for(i=3;i<=n;i++)
 {
 while(top>=2&&cj(stack1[top-1],stack1[top],f[i])<=0)
 {
 top--;
 }
 stack1[++top]=f[i];
 } 
 double sum=0;
 for(i=0;i<top;i++)
 sum+=jl(stack1[i],stack1[i+1]);
 printf("%.2lf\n",sum);
 }
 }
 }

TOJ 3100 女生寝室的围墙 ![20171202143949563][]

#include<stdio.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 #define PI acos(-1.0)
 //比凸包多加了一个圆的周长。 
 struct point
 {
 double x,y;
 }f[1050],stack1[1050];
 double jl(point p1,point p2)
 {//距离
 return (double)sqrt(1.0*(p1.x-p2.x)*(p1.x-p2.x)+1.0*(p1.y-p2.y)*(p1.y-p2.y));
 }
 double cj(point p0,point p1,point p2)
 {//差积 
 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 }
 bool cmp(point u,point w)
 {//排序
 double x=cj(f[0],u,w);
 if(x>0)return true;
 else if(x<0)return false;
 double len1=jl(f[0],u);
 double len2=jl(f[0],w);
 return len1<len2;
 }
 int main()
 {
 int n,m,i,j,top;
 double sum;
 while(scanf("%d%d",&n,&m)!=EOF)
 { 	
 if(n==0)break;
 sum=0;
 for(i=0;i<n;i++)
 scanf("%lf%lf",&f[i].x,&f[i].y);
 if(n==1)
 {
 	 	sum+=2*PI*m;
 			printf("%.0lf\n",sum);
 continue;
 }
 else if(n==2)
 {
 	sum+=2*PI*m;
 		 	sum+=jl(f[0],f[1])*2;
 		 	printf("%.0lf\n",sum);
 continue;
 }
 else
 {
 top=2;
 for(i=1;i<n;i++)
 {
 if(f[i].y<f[0].y||(f[i].y==f[0].y&&f[i].x<f[0].x))
 swap(f[0],f[i]);
 }
 sort(f+1,f+n,cmp);
 f[n]=f[0];
 	for(i=0;i<=2;i++)
 	stack1[i]=f[i];
 for(i=3;i<=n;i++)
 {
 while(top>=2&&cj(stack1[top-1],stack1[top],f[i])<=0)
 {
 top--;
 }
 stack1[++top]=f[i];
 } 
 for(i=0;i<top;i++)
 sum+=jl(stack1[i],stack1[i+1]);
 sum+=2*PI*m;
 			printf("%.0lf\n",sum);
 }
 }
 }

[20171202143352740]: /images/20220604/06036ab8b9f84677928f34715e9cf65e.png
[20171202143636420]: /images/20220604/82f703add83c4c0eb7e503c8b5a48363.png
[20171202143748787]: /images/20220604/d12cc9016c904daeaf2d1c331c2cbb68.png
[20171202143949563]: /images/20220604/69ab87102b78452895aa781f011cdcd9.png