POJ 1113 Wall (经典的基础凸包, Graham)

题目传送门:http://poj.org/problem?id=1113

分析:经典的凸包问题,且是最适合入门的一道凸包问题,我是用Graham Scan做的。题目给定一个简单多边形,求外围大于L的周长,由题目分析可知,只需要求出这个给定多边形的凸包,再加上一个以L为半径的圆周长即可,因为按照题意,距离多边形外围L的一个图形,由直线和圆弧组成,而所有的圆弧加起来就是一个圆形了(?为什么?自己画个图看看,所有圆弧的较就是多边形的内角,加起来就是2*PI)。所以~~~

AC代码,有点暴力,所以耗时200+ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
const int MAXN = 1005;
const double PI = acos(-1.0);
 
typedef struct Point{
	int x;
	int y;
}Point;
 
Point p[MAXN]; // 保存输入结点
Point que[MAXN];  // 保存凸包结点,把que当一个栈来使用
int top;          // 记录栈顶位置
 
// 求a, b两点距离
double dis(Point a, Point b)
{
	return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
}
 
// 求P0P1与P0P2的叉积
//叉乘,如果大于0,则说明直线P0P1在P0P2的顺时针方向,即P0P1在P0P2下面
int cross(Point p1,Point p2, Point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
 
// 用GrahamScan求凸包
void GrahamScan(int n)
{
	Point tmp;
	int k = 0;
	// ![0] 找出y值(y值相同时找x最小)最小的点作为起始点P0
	for(int i=1; i<n; ++i)
		if((p[i].y < p[k].y) || ((p[i].y==p[k].y) && (p[i].x<p[k].x)))
			k = i;
	tmp = p[0];
	p[0] = p[k];
	p[k] = tmp;
	// ![0]
 
	// ![1] 按极角大小逆时针排序
	for(int i=1; i<n; ++i)
	{
		k = i;
		for(int j=i+1; j<n; ++j)
			if((cross(p[j], p[k], p[0]) > 0)
				|| (cross(p[j], p[k], p[0])==0 && dis(p[0], p[j])<dis(p[0], p[k])))
				k = j;
		tmp = p[i];
		p[i] = p[k];
		p[k] = tmp;
	}
	// ![1]
 
	// ![2] 先把极角最小的0, 1, 2三点存入栈中
	top = -1;
	que[++top] = p[0];
	que[++top] = p[1];
	que[++top] = p[2];
	// ![2]
 
	// ![3] 从第3点开始,直到最后,如果不能左转,则退栈,这个具体看《算法导论》P586上图例分析
	for(int i=3; i<n; ++i)
    {
        while((cross(p[i], que[top],que[top-1]))>=0)    //如果不能左转,则退栈
             top--;
        que[++top]=p[i];
    }
	// ![3]
 
	// ![4] 最后记得top要加1
	top++;
	// ![4]
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	int N, L;
	cin >> N >> L;
	for(int i=0; i<N; ++i)
		cin >> p[i].x >> p[i].y;
	GrahamScan(N);
	double ans = 0.0;
	for(int i=0; i<top; ++i)
		ans += dis(que[i], que[(i+1)%top]);
	ans += 2*PI*L;
	cout << (int)(ans+0.5) << endl;
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 1113 Wall (经典的基础凸包, Graham)》有140个想法

  1. 也是初学 ,但是觉得你很赞 !

    Tanky Woo,业余的编程爱好者,喜欢C/C++,目前正在学习Qt,热爱算法,钟情于OJ的各种水题,未曾参加任何ACM比赛。每一次A题,只为怡情。

发表评论

电子邮件地址不会被公开。 必填项已用*标注