题目大意：求一个点集凸包边长
题解：求凸包，直接求
卡点：发现在较后面数位上有较小的误差，还以为是浮点数误差，最后发现是构造函数写成了$int$类型
C++ Code：
#include#include #include #include #include #define maxn 10010inline double sqr(double x) { return x * x; }struct Point { double x, y; Point() { } Point(double __x, double __y) : x(__x), y(__y) { } inline Point operator - (const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); } inline Point operator + (const Point &rhs) const { return Point(x + rhs.x, y + rhs.y); } inline double operator * (const Point &rhs) const { return x * rhs.y - y * rhs.x; }} O, s[maxn], v[maxn];inline double abs2(const Point &x) { return sqr(x.x) + sqr(x.y); }inline double dis(const Point &lhs, const Point &rhs) { return sqrt(abs2(rhs - lhs)); }inline double det(const Point &O, const Point &lhs, const Point &rhs) { return (lhs - O) * (rhs - O);}inline bool operator < (const Point &lhs, const Point &rhs) { static Point X, Y; X = lhs - O, Y = rhs - O; static double t; t = X * Y; return (t > 0) || (t == 0 && abs2(X) > abs2(Y));}int n, tot;int main() { std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); std::cin >> n; if (n <= 1) { std::cout << "0\n"; return 0; } int miny = 0; for (int i = 0; i < n; ++i) { std::cin >> s[i].x >> s[i].y; if ((s[i].y < s[miny].y) || (s[i].y == s[miny].y && s[i].x < s[miny].x)) miny = i; } if (n == 2) { std::cout << std::fixed << std::setprecision(2) << dis(s[0], s[1]) * 2 << '\n'; return 0; } O = s[miny]; std::swap(s[0], s[miny]); std::sort(s + 1, s + n); v[0] = s[0], v[1] = s[1], v[2] = s[2], tot = 3; for (int i = 3; i < n; ++i) { for (Point a = v[tot - 2], b = v[tot - 1]; tot > 2 && det(a, b, s[i]) <= 0; a = v[tot - 2], b = v[tot - 1]) --tot; v[tot++] = s[i]; } double ans = 0; for (int i = 0, nxt = 0; i < tot; ++i) { nxt += 1 - tot; nxt += nxt >> 31 & tot; ans += dis(v[i], v[nxt]); } std::cout << std::fixed << std::setprecision(2) << ans << '\n'; return 0;}