欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 1113 凸包问题

程序员文章站 2022-03-29 21:23:11
...

我的第一道凸包题,终于弄懂了Graham算法,对我来说弄懂一个算法是一个痛苦的过程,我痛苦了我好几天……

Grahma算法模板:

1、  寻找一个基准点,这个点通常是最左边的最下面那个点(其实只要这个点一定会在凸包边界上就行),然后将之个点置于第一个位置。

2、  将所有点按相对于基准点的极角排序。

3、  因为排序之后前两个点一定会在凸包上,假设第三个点也在凸包上,因此我们可以从第四个点开始依次扫描每个点。对于每个当前点他在当前时刻是极角最大的点,所以在当前时刻它必定在凸包上,那么此时就可能改变了它前一个点是不是在凸包上。怎么判断呢?我们可以咱当前点到推三个点,假设是p1,p2,p3,判断这三个点所形成的角是不是大于180度,小于180度继续扫描下一个点,若大于180度说明第二个点一定在凸包内部,然后我们暂时停止扫描下一个点,将p1,p2各自后退一个点继续判断p1,p2,p3所组成的角是不是大于180度,(这也就是所谓的“退化”问题,看了《算法导论》后才知道这儿需要有个循环)若仍然大于180度循环这种操作直到三个点组成的角小于等于180度,最后继续扫描下一个点,直到结束。在这个过程中我们可以用栈来保存凸包边上的点。

该题需要最后算出各边长的和再加上圆的周长。

#include<iostream>
#include<cmath>
using namespace std;
#define MAX_INT 123456789
struct point
{
	int x,y;
};
point vertex[1001],stack[1000];
int angle(point p1,point p2,point p0)//判断极角大小
{	
	return (p1.y-p0.y)*(p2.x-p0.x)-(p2.y-p0.y)*(p1.x-p0.x);
}
int dist(point p1,point p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int cmp(const void* pp,const void* qq)//排序判断条件
{
	point p1,p2;
	p1=*(point*) pp; p2=*(point*) qq;
	if(angle(p1,p2,vertex[0])>0)
		return 1;
	else if(angle(p1,p2,vertex[0])==0 && dist(p1,vertex[0])>dist(p2,vertex[0]))
		return 1;
	return -1;
}
int judge(point p1,point p2,point p3)//判断三点组成的角度
{
	return (p3.y-p2.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p2.x);
}
double Graham(int n,int m)
{
	int sum_max=0,i=0;  
	point p1,p2;
	double sum=0;
	p1=vertex[1],p2=vertex[2];
	stack[0]=vertex[0];
	stack[1]=vertex[1];
	stack[2]=vertex[2];
	sum_max=2;
	for(i=3;i<n;i++)
	{
		while(1)//解决退化问题
		{
			if(judge(p1,p2,vertex[i])>=0)
			{
				p1=p2,p2=vertex[i];   
				stack[++sum_max]=vertex[i];
				break;
			}
			else
			{
				--sum_max;
				p2=stack[sum_max];
				p1=stack[sum_max-1];
			}
		}
	}
	for(i=0;i<sum_max;i++)
		sum+=sqrt((double)dist(stack[i],stack[i+1]));
	sum+=sqrt((double)dist(stack[sum_max],vertex[0]))+3.1415926*2*m;
	return sum;
}
int main()
{
	int i,m,n,min;
	point minPoint;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(vertex,0,sizeof(vertex));
		minPoint.x=minPoint.y=MAX_INT;
		for(min=i=0;i<n;i++)
		{
			scanf("%d%d",&vertex[i].x,&vertex[i].y);
			if(minPoint.x>vertex[i].x) 
			{
				minPoint=vertex[i];
                min=i;
			}
			else if(minPoint.x==vertex[i].x && minPoint.y>vertex[i].y)
			{
				minPoint=vertex[i];
				min=i;
			}
		}
        vertex[min]=vertex[0]; vertex[0]=minPoint;
		qsort(vertex+1,n-1,sizeof(vertex[0]),cmp);

		printf("%.lf\n",Graham(n,m));
	}
	return 0;
}

 

转载于:https://www.cnblogs.com/yu-chao/archive/2011/11/05/2237018.html

上一篇: frp实现内网穿透

下一篇: testing