WA #16 求助

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(...) cerr << format(__VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
template<typename T> void ckmax(T& a, T b) { if (a < b) a = b; }
template<typename T> void ckmin(T& a, T b) { if (b < a) a = b; }

#ifndef PROGRAM_MAIN_CALC_GEOM_CS_
#define PROGRAM_MAIN_CALC_GEOM_CS_
namespace cg {
  using f64 = double;
  using i64 = int64_t;
  constexpr f64 eps = 1e-8;
  int sgn(f64 a) {
    return (a > eps) - (a < -eps);
  }
  int sgn(i64 a) {
    return (a > 0) - (a < 0);
  }
  template<typename T>
  struct point {
    T x, y;
    point() {}
    point(T x_, T y_): x{x_}, y{y_} {}
    template<typename U>
    point(const point<U>& o): x{static_cast<T>(o.x)}, y{static_cast<T>(o.y)} {};
    template<typename U>
    point(point<U>&& o): x{static_cast<T>(o.x)}, y{static_cast<T>(o.y)} {};
    template<typename U>
    point<T>& operator=(const point<U>& o) {x = static_cast<T>(o.x); y = static_cast<T>(o.y); return *this;}
    template<typename U>
    point<T>& operator=(point<T>&& o) {x = static_cast<T>(o.x); y = static_cast<T>(o.y); return *this;}
    template<typename U>
    auto operator+(point<U> other) -> point<decltype(x + other.x)> {
      return point<decltype(x + other.x)>(x + other.x, y + other.y);
    }
    template<typename U>
    auto operator-(point<U> other) -> point<decltype(x - other.x)> {
      return point<decltype(x - other.x)>(x - other.x, y - other.y);
    }
    template<typename U>
    auto operator*(U k) -> point<decltype(x * k)> {
      return point<decltype(x * k)>(x * k, y * k);
    }
    template<typename U>
    auto operator/(U k) -> point<decltype(x / k)> {
      return point<decltype(x / k)>(x / k, y / k);
    }
    template<typename U>
    bool operator==(point<U> other) {
      return sgn(x - other.x) == 0 && sgn(y - other.y) == 0;
    }
  };
  template<typename T>
  using vctor = point<T>;
  template<typename T>
  T dot(vctor<T> a, vctor<T> b) {
    return a.x * b.x + a.y * b.y;
  }
  template<typename T>
  T cross(vctor<T> a, vctor<T> b) {
    return a.x * b.y - a.y * b.x;
  }
  template<typename T>
  T sqr(T a) {
    return a * a;
  }
  template<typename T>
  f64 dist_sqrt(point<T> a, point<T> b) {
    return hypot(a.x - b.x, a.y - b.y);
  }
  template<typename T>
  T dist_sqr(point<T> a, point<T> b) {
    return sqr(a.x - b.x) + sqr(a.y - b.y);
  }
  template<typename T>
  struct line {
    point<T> a, b;
    line() {}
    line(point<T> c, point<T> d): a(c), b(d) {}
    line(f64 c, f64 d, f64 e) {
      if (sgn(c) == 0) {
        a = point<T>(0, -c/b);
        b = point<T>(1, -c/b);
      } else if (sgn(b) == 0) {
        a = point<T>(-c/a, 0);
        b = point<T>(-c/a, 1);
      } else {
        a = point<T>(0, -c/b);
        b = point<T>(1, (-c-a)/b);
      }
    }
    template<typename U>
    line(const line<U>& o): a(o.a), b(o.b) {}
    template<typename U>
    line(line<U>&& o): a(o.a), b(o.b) {}
    template<typename U>
    line<T>& operator=(const line<U>& o) {a = o.a; b = o.b; return *this;}
    template<typename U>
    line<T>& operator=(line<U>&& o) {a = move(o.a); b = move(o.b); return *this;}
  };
  template<typename T>
  using segment = line<T>;
  template<typename T>
  f64 dist_point_line(point<T> a, line<T> b) { // 面积 / 底
    return fabs(cross(b.a - a, b.b - a)) / dist_sqrt(b.a, b.b);
  }
}
#endif

using i64 = int64_t;
int N;
vector<cg::point<i64>> a, d_line, u_line;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> N;
  a.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i].x >> a[i].y;
  }
  ranges::sort(a, [&](const cg::point<i64>& a, const cg::point<i64>& b) {return cg::sgn(a.x - b.x) < 0 || (cg::sgn(a.x - b.x) == 0 && cg::sgn(a.y - b.y) < 0);});
  for (int i = 0; i < N; ++i) {
    int len_d = static_cast<int>(d_line.size());
    while (len_d >= 2 && cg::cross(d_line[len_d - 1] - d_line[len_d - 2], a[i] - d_line[len_d - 1]) <= 0) {
      d_line.pop_back();
      --len_d;
    }
    d_line.push_back(a[i]);
  }
  for (int i = N - 1; i >= 0; --i) {
    int len_u = static_cast<int>(u_line.size());
    while (len_u >= 2 && cg::cross(u_line[len_u - 1] - u_line[len_u - 2], a[i] - u_line[len_u - 1]) <= 0) {
      u_line.pop_back();
      --len_u;
    }
    u_line.push_back(a[i]);
  }
  if (u_line.front() == d_line.back()) d_line.pop_back();
  if (d_line.front() == u_line.back()) u_line.pop_back();

  vector<cg::point<i64>> ch;
  ch.reserve((d_line.size() + u_line.size()) << 1);
  ranges::move(d_line, back_inserter(ch));
  ranges::move(u_line, back_inserter(ch));
  int len_ch = static_cast<int>(ch.size());
  i64 ans = 0;
  {
    cg::line<i64> l;
    for (int i = 0, j = 0; i < len_ch; ++i) {
      l = cg::line<i64>(ch[i], ch[(i + 1) % len_ch]);
      while (cg::dist_point_line(ch[(j + 1) % len_ch], l) > cg::dist_point_line(ch[j], l)) {
        j = (j + 1) % len_ch;
      }
      ckmax(ans, max(cg::dist_sqr(ch[j], ch[i]), cg::dist_sqr(ch[j], ch[(i + 1) % len_ch])));
    }
  }
  cout << ans << '\n';
  return 0;
}