计算几何:凸包

对于初学计算几何的OIer来说,Graham算法是个不错的凸包算法。Graham算法相比极角排序法来说,更为直观也更容易理解。

数据定义

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
class Point {
public:
double x, y;

Point(double x = 0, double y = 0):x(x), y(y) {}

Point(Point a, Point b) {
//构造从a到b的向量
x = b.x - a.x;
y = b.y - a.y;
}

double dist(const Point& p) const {
//计算从自身到点P的距离
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}

double operator * (const Point& p) const {
//计算向量叉积
return x * p.y - p.x * y;
}

bool operator < (const Point& p) const {
//按照X轴排序
return (x == p.x) ? (y < p.y) : (x < p.x);
}

friend istream& operator >> (istream& in, Point& p) {
//重载 >> 运算符使得cin可以输入
in >> p.x >> p.y;

return in;
}
};

const int MAXN = 10000 + 5;

Point p[MAXN];
int st[MAXN], top = -1; //点栈
int n;

主程序

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
void input() { //输入所有点
cin >> n;
for(int i = 0; i < n; i++) {
cin >> p[i];
}
}

int main() {
input();
sort(p, p + n); //对点进行直角坐标排序􏰣􏰳􏰣􏰳􏰮􏰂
double ans = 0;

st[++top] = 0; //将第一个点入栈
st[++top] = 1; //将第二个点入栈

for(int i = 2; i < n; i++) {
Point u(p[st[top - 1]], p[st[top]]); //计算栈顶两个点构成的向量
Point v(p[st[top]], p[i]); //计算当前点与栈顶构成的向量

while(u * v < 0) { //若叉积小于0
if(top == 0) { //当栈中只有一个元素时,退出循环
break;
}
top--; //弹出栈顶
u = Point(p[st[top - 1]], p[st[top]]); //更新
v = Point(p[st[top]], p[i]); //更新
}
st[++top] = i; //将第i个点压入栈中
}

for(int i = 0; i <= top - 1; i++) {
ans += p[st[i]].dist(p[st[i + 1]]); //累加下半个凸包的长度
}
top = -1; //清空栈

//求出上半个凸包,与前半部分大同小异
st[++top] = 0;
st[++top] = 1;

for(int i = 2; i < n; i++) {
Point u(p[st[top - 1]], p[st[top]]);
Point v(p[st[top]], p[i]);

while(u * v > 0) {
if(top == 0) {
break;
}
top--;
u = Point(p[st[top - 1]], p[st[top]]);
v = Point(p[st[top]], p[i]);
}
st[++top] = i;
}

for(int i = 0; i <= top - 1; i++) {
ans += p[st[i]].dist(p[st[i + 1]]);
}
top = -1;

cout << setprecision(2) << fixed << ans << endl; //控制精度

return 0;
}
文章作者: Helium
文章链接: https://keepthethink.github.io/archives/704167021/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Heliumの博客