【凸包Graham_Scan算法】HDU 1348 Wall

http://acm.hdu.edu.cn/showproblem.php?pid=1348

典型凸包题，求外围城墙的周长
Sample Input
1
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

Sample Output
1628

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define PI 3.14159265

struct point{
	double x, y, angel;
}p[1005], ch[1005];

double dist (point a, point b)
{
	return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double multi (point a, point b, point c)
{
	double x1, y1, x2, y2;
	x1 = b.x - a.x;
	y1 = b.y - a.y;
	x2 = c.x - b.x;
	y2 = c.y - b.y;
	return x1*y2 - x2*y1;
}

bool cmp (point a, point b)
{
	if (a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}

bool cmp2 (point a, point b)
{
	if (a.angel == b.angel)
	{
		if (a.x == b.x)
			return a.y > b.y;
		return a.x > b.x;
	}
	return a.angel < b.angel;
}

int main()
{
	int n, i, top, t;
	double r, len;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%lf", &n, &r);
		for (i = 0; i < n; i++)
			scanf ("%lf%lf", &p[i].x, &p[i].y);
		sort (p, p+n, cmp);    //找到左下角的p[0]

		//找相对于p[0]的极角，并把除了p[0]以外的点按照极角排序
		for (i = 1; i < n; i++)
			p[i].angel = atan2 (p[i].y-p[0].y, p[i].x-p[0].x);
		sort (p+1, p+n, cmp2);

		//Graham_Scan算法
		ch[0] = p[0], ch[1] = p[1], ch[2] = p[2];
		top = 3;
		for (i = 3; i < n; i++)
		{
			while (top > 2 && multi (ch[top-2], ch[top-1], p[i]) <= 0)
				top--;
			ch[top++] = p[i];
		}

		//求周长
		len = dist (ch[0], ch[top-1]);
		for (i = 1; i < top; i++)
			len += dist (ch[i], ch[i-1]);
		len += 2 * PI * r;    //加上圆弧，刚好为一个圆！

		printf ("%.0lf\n", len);
		if (t)
			printf ("\n");
	}
	return 0;
}

评论

2 楼 基德KID.1412 2011-08-08  

gzhu_101majia 写道

就是poj1113 我blog有啊 看看啊

早就看过了，只是今天总结下下

1 楼 gzhu_101majia 2011-08-08  

就是poj1113 我blog有啊 看看啊