凸包 hdu1392

2017年08月09日 11点热度 0人点赞 0条评论

题意:求凸包的周长

#include
#include
#include
#include
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);
int sgn(double x) {
	if(fabs(x) < eps)return 0;
	if(x < 0)return -1;
	else return 1;
}
struct Point {
	double x,y;
	Point() {}
	Point(double _x,double _y) {
		x = _x;
		y = _y;
	}
	Point operator -(const Point &b)const {
		return Point(x - b.x,y - b.y);
	}
//叉积
	double operator ^(const Point &b)const {
		return x*b.y - y*b.x;
	}
//点积
	double operator *(const Point &b)const {
		return x*b.x + y*b.y;
	}
//绕原点旋转角度B(弧度值),后x,y的变化
	void transXY(double B) {
		double tx = x,ty = y;
		x = tx*cos(B) - ty*sin(B);
		y = tx*sin(B) + ty*cos(B);
	}
};
double dist(Point a,Point b) {
	return sqrt((a-b)*(a-b));
}

const int MAXN = 1010;
Point list[MAXN];
int Stack[MAXN],top;
//相对于list[0]的极角排序
bool _cmp(Point p1,Point p2) {
	double tmp = (p1-list[0])^(p2-list[0]);
	if(sgn(tmp) > 0)return true;
	else if(sgn(tmp) == 0 && sgn(dist(p1,list[0]) - dist(p2,list[0])) <= 0)
		return true;
	else return false;
}
void Graham(int n) {
	Point p0;
	int k = 0;
	p0 = list[0];
//找最下边的一个点
	for(int i = 1; i < n; i++) {
		if( (p0.y > list[i].y) || (p0.y == list[i].y && p0.x > list[i].x) ) {
			p0 = list[i];
			k = i;
		}
	}
	swap(list[k],list[0]);
	sort(list+1,list+n,_cmp);
	if(n == 1) {
		top = 1;
		Stack[0] = 0;
		return;
	}
	if(n == 2) {
		top = 2;
		Stack[0] = 0;
		Stack[1] = 1;
		return ;
	}
	Stack[0] = 0;
	Stack[1] = 1;
	top = 2;
	for(int i = 2; i < n; i++) {
		while(top > 1 &&
		        sgn((list[Stack[top-1]]-list[Stack[top-2]])^(list[i]-list[Stack[top-2]])) <=
		        0)
			top--;
		Stack[top++] = i;
	}
}
int main(){
	int n;
	while(~scanf("%d",&n)&&n)
	{
		for(int i=0;ix),&((list+i)->y));
		Graham(n);
		double ans=0;
		for(int i=1;i2) ans+=dist(list[Stack[0]],list[Stack[top-1]]);
		printf("%.2fn",ans);
	}
	return 0;
}
未经允许不得转载!凸包 hdu1392

update

纸上得来终觉浅, 绝知此事须躬行。