题目地址：

农夫约翰想要建造一个围栏来围住奶牛。构建这个围栏时，必须将若干个奶牛们喜爱的地点都包含在围栏内。现在给定这些地点的具体坐标，请你求出将这些地点都包含在内的围栏的最短长度是多少。注意：围栏边上的点也算处于围栏内部。

输入格式： 第一行包含整数 N N N，表示奶牛们喜爱的地点数目。 接下来 N N N行，每行包含两个实数 X i , Y i X_i,Y_i Xi,Yi，表示一个地点的具体坐标。

输出格式： 输出一个实数，表示围栏最短长度。保留两位小数。

数据范围： 0 ≤ N ≤ 10000 0≤N≤10000 0≤N≤10000 − 1 0 6 ≤ X i , Y i ≤ 1 0 6 −10^6≤X_i,Y_i≤10^6 −106≤Xi,Yi≤106 数据保证所有奶牛不会全部处在同一条直线上。

#include <iostream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
using PDD = pair<double, double>;

const int N = 10010;
int n;
PDD q[N];
int stk[N];
// used[i]表示下标i的点是否用过
bool used[N];

double get_dist(PDD a, PDD b) {
          
   
  double dx = a.x - b.x, dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}

PDD operator-(PDD &a, PDD &b) {
          
   
  return {
          
   a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b) {
          
   
  return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c) {
          
   
  return cross(b - a, c - a);
}

double andrew() {
          
   
  int top = 0;
  for (int i = 0; i < n; i++) {
          
   
    // 形成右手系了，就出栈
    while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) >= 0)
      used[stk[--top]] = false;
    stk[top++] = i;
    used[i] = true;
  }

  used[0] = false;
  for (int i = n - 1; i >= 0; i--) {
          
   
    if (used[i]) continue;
    while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) >= 0)
      top--;
    stk[top++] = i;
  }

  double res = 0;
  for (int i = 1; i < top; i++)
    res += get_dist(q[stk[i - 1]], q[stk[i]]);

  return res;
}

int main() {
          
   
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
  // 排序并去重
  sort(q, q + n);
  int idx = 1;
  for (int i = 1; i < n; i++) if (q[i] != q[idx - 1]) q[idx++] = q[i];
  n = idx;
  printf("%.2lf
", andrew());
}

时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间 O ( n ) O(n) O(n)。