欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

POJ 1113 Wall(思维 计算几何 数学)

程序员文章站 2024-01-16 15:32:16
题意 "题目链接" 给出平面上n个点的坐标。你需要建一个围墙,把所有的点围在里面,且围墙距所有点的距离不小于l。求围墙的最小长度。 $n \leqslant 10^5$ Sol 首先考虑如果没有l的限制,那么显然就是凸包的长度。 现在了距离的限制,那么显然原来建在凸包上的围墙要向外移动$l$的距离, ......

题意

给出平面上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);
}