采用Andrew算法求解计算几何中的二维凸包问题
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-6
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 100001;
int sgn(double x)
{
if (fabs(x) < EPS)
return 0;
else
return x < 0 ? -1 : 1;
}
struct Point
{
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator+(Point B) { return Point(x + B.x, y + B.y); }
Point operator-(Point B) { return Point(x - B.x, y - B.y); }
bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
bool operator<(Point B) { return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0); }
};
typedef Point Vector;
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); }
int Convex_hull(Point *p, int n, Point *ch)
{
n = unique(p, p + n) - p;
sort(p, p + n);
int v = 0;
for (int i = 0; i < n; i++)
{
while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
int j = v;
for (int i = n - 2; i >= 0; i--)
{
while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
if (n > 1)
v--;
return v;
}
Point p[N], ch[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
int v = Convex_hull(p, n, ch);
double ans = 0;
for (int i = 0; i < v; i++)
ans += Distance(ch[i], ch[(i + 1) % v]);
printf("%.2lf\n", ans);
return 0;
}