题目链接
分析： 题目要求通过1和 2√ 长度的边把给定的点全部围起来，于是很容易想到求一个凸包，然后长度1个数为 max(abs(x1−x2),abs(y1−y2))−min(abs(x1−x2),abs(y1−y2)) , 长度为 2√ 的为 min(abs(x1−x2),abs(y1−y2)) 。 需要注意的是叉积会爆int
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <queue> #include <deque> #include <stack> #include <set> #include <cmath> using namespace std; struct Point { int x, y; Point (int x = 0, int y = 0) : x(x), y(y) {} bool operator <(const Point &rhs) const { if (rhs.x == x) return y < rhs.y; return x < rhs.x; } }; typedef Point Vector; Vector operator +(Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator -(Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); } long long Cross(Vector A, Vector B) { return 1ll * A.x * B.y - 1ll * A.y * B.x; } int ConvexHull(Point *p, int n, Point *ch) { sort(p, p + n); int m = 0; for (int i = 0; i < n; i ++) { while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m --; ch[m ++] = p[i]; } int k = m; for (int i = n - 2; i >= 0; i --) { while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m --; ch[m ++] = p[i]; } if (n > 1) m --; return m; } const int maxn = 1e4 + 5; Point node[maxn], hull[maxn]; long long resa, resb; void work(const Point &a, const Point &b) { int minv = min(abs(a.x - b.x), abs(a.y - b.y)); int maxv = max(abs(a.x - b.x), abs(a.y - b.y)); resb += 1ll * minv; resa += 1ll * (maxv - minv); } int main() { int N; while (~scanf("%d", &N) && N) { resa = 0, resb = 0; for (int i = 0; i < N; i++) scanf("%d%d", &node[i].x, &node[i].y); int len = ConvexHull(node, N, hull); for (int i = 1; i < len; i ++) { // cout<<hull[i - 1].x<<" "<<hull[i - 1].y<<" "<<hull[i].x<<" "<<hull[i].y<<endl; work(hull[i - 1], hull[i]); } work(hull[0], hull[len - 1]); printf("%lld %lld\n", resa, resb); } return 0; }