G24 凸包算法 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P2742 ↗

题目描述

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

输入格式

输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 $n$ 。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数 $x_i, y_i$ 分别代表第 $i$ 个放牧点的横纵坐标。

输出格式

输出输出一行一个四舍五入保留两位小数的实数，代表围栏的长度。

输入输出样例 #1

输入 #1

plaintext

输出 #1

12.00

plaintext

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$ ， $-10^6 \leq x_i, y_i \leq 10^6$ 。小数点后最多有 $2$ 位数字。

算法解析：#

Andrew 凸包：按 $(x,y)$ 排序后，先从左到右构造下凸包，再从右到左构造上凸包，用叉积判断转向（ $\le0$ 弹出栈顶）。最后栈中即凸包顶点，相邻点距离求和得周长。 $O(n\log n)$ 。

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=100010;
struct Point{double x,y;} p[N],s[N];
int n,top;

double cross(Point a,Point b,Point c){ //叉积
  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double dis(Point a,Point b){ //距离
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(Point a, Point b){ //比较
  return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
double Andrew(){
  sort(p+1,p+n+1,cmp); //排序
  for(int i=1; i<=n; i++){ //下凸包
    while(top>1&&cross(s[top-1],s[top],p[i])<=0)top--;
    s[++top]=p[i];
  }
  int t=top;
  for(int i=n-1; i>=1; i--){ //上凸包
    while(top>t&&cross(s[top-1],s[top],p[i])<=0)top--;
    s[++top]=p[i];
  }
  double res=0; //周长
  for(int i=1; i<top; i++) res+=dis(s[i],s[i+1]);
  return res;
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
  printf("%.2lf\n", Andrew());
  return 0;
}