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

const int MAXN = ?;	// n 的最大值

struct point {
	int x;
	int y;
	point operator - (const point &p) const {
		point ret;
		ret.x = x - p.x;
		ret.y = y - p.y;
		return ret;
	}
} p[MAXN];	// 点集数组
int n;	// 点的个数

// 水平序的排序比较函数
bool cmp(point a, point b) {
	if(a.y != b.y) return a.y < b.y;
	else return a.x < b.x;
}

// Det 和 Cross 函数用于计算叉积
int Det(int x1, int y1, int x2, int y2) {
	return x1*y2 - x2*y1;
}

int Cross(point a, point b, point p) {
	return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

// 计算平面上两点间直线距离
int CalculateDistance(point a, point b) {
	point p = a - b;

	return p.x*p.x + p.y*p.y;
}

// Graham's Scan 算法（水平序）
void GrahamScan() {
	sort(p, p+n, cmp);	// 水平序排序
	point res[MAXN];	// 用来记录求得的凸包点集
	int top = 0;
	for(int i=0; i<n; ++i) {	// 反向扫描右链
		while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
			top--;
		}
		res[top++] = p[i];
	}
	int tmp = top;
	for(int i=n-2; i>=0; --i) {	// 扫描左链
		// "top>tmp" 用于保证右链已生成的点不会被左链扫描所影响
		while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
			top--;
		}
		res[top++] = p[i];
	}
}

 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

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 50000;

struct point {
	int x;
	int y;
	point operator - (const point &p) const {
		point ret;
		ret.x = x - p.x;
		ret.y = y - p.y;
		return ret;
	}
} p[MAXN];
int n;

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

int Det(int x1, int y1, int x2, int y2) {
	return x1*y2 - x2*y1;
}

int Cross(point a, point b, point p) {
	return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

int CalculateDistance(point a, point b) {
	point p = a - b;

	return p.x*p.x + p.y*p.y;
}

int GrahamScan() {
	sort(p, p+n, cmp);
	point res[MAXN];
	int top = 0;
	for(int i=0; i<n; ++i) {
		while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
			top--;
		}
		res[top++] = p[i];
	}
	int tmp = top;
	for(int i=n-2; i>=0; --i) {
		while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
			top--;
		}
		res[top++] = p[i];
	}
	int ans = 0;
	// 枚举凸包上的所有点对
	for(int i=0; i<top-2; ++i) {
		for(int j=i+1; j<top-1; ++j) {
			ans = max(ans, CalculateDistance(res[i], res[j]));
		}
	}

	return ans;
}

int main(int argc, char const *argv[]) {
	scanf("%d", &n);
	for(int i=0; i<n; ++i) {
		scanf("%d %d", &p[i].x, &p[i].y);
	}
	printf("%d\n", GrahamScan());
	
	return 0;
}