题意

题目链接

给出平面上n个点的坐标。你需要建一个围墙，把所有的点围在里面，且围墙距所有点的距离不小于l。求围墙的最小长度。

\(n \leqslant 10^5\)

Sol

首先考虑如果没有l的限制，那么显然就是凸包的长度。

现在了距离的限制，那么显然原来建在凸包上的围墙要向外移动\(l\)的距离，同时会增加一些没有围住的位置

因为多边形的外交和为360，再根据补角的性质，画一画图就知道这一块是一个半径为\(l\)的圆。

因为总答案为凸包周长 + \(2 \pi l\)

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, top;

struct Point {

	double x, y;

	Point operator - (const Point &rhs) const {

		return {x - rhs.x, y - rhs.y};

	}

	Point operator + (const Point &rhs) const {

		return {x + rhs.x, y + rhs.y};

	}

	double operator ^ (const Point &rhs) const {

		return x * rhs.y - y * rhs.x;

	}

	bool operator < (const Point &rhs) const {

		return x == rhs.x ? y < rhs.y : x < rhs.x;

	}

}p[MAXN], q[MAXN];

template<typename A> A sqr(A x) {

	return x * x;

}

double dis(Point a, Point b) {

	return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));

}

void insert(Point now) {

	while(top > 1 && ((q[top] - q[top - 1]) ^ (now - q[top - 1])) < 0) top--;

	q[++top] = now;

}

int main() {

	N = read(); double L = read();

	for(int i = 1; i <= N; i++) p[i].x = read(), p[i].y = read();

	sort(p + 1, p + N + 1);

	q[top = 1] = p[1];

	for(int i = 2; i <= N; i++) insert(p[i]);

	for(int i = N - 1; i >= 1; i--) insert(p[i]);

	double ans = 0;

	for(int i = 1; i < top; i++) ans += dis(q[i], q[i + 1]);

	ans += 2 * acos(-1) * L + 0.5;

	printf("%d\n", (int) ans);

}