QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#640#425332#784. 旋转卡壳yzy1yzy1Failed.2024-05-30 08:58:122024-05-30 08:58:12

详细

Extra Test:

Invalid Input

input:

10
0 0
10000 0
1 100
2 199
9999 100
9998 199
100 -900
200 -1799
9800 -1799
9900 -900

output:


result:

FAIL convex, i = 0

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425332#784. 旋转卡壳yzy197 193ms33516kbC++232.7kb2024-05-30 08:44:452024-05-30 09:01:42

answer

#include <bits/stdc++.h>

#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif

using namespace std;

using ll = long long;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
  if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
  if (y < x) x = y;
}

struct P {
  double x = 0, y = 0;
  inline int Q() const { return (y < 0) << 1 | ((x < 0) ^ (y < 0)); }
  inline double Norm2() const { return x * x + y * y; }
};

inline P operator+(P x, P y) { return {x.x + y.x, x.y + y.y}; }
inline P operator*(P x, double y) { return {x.x * y, x.y * y}; }
inline P operator-(P x, P y) { return {x.x - y.x, x.y - y.y}; }
inline double operator*(P x, P y) { return x.x * y.x + x.y * y.y; }
inline double operator^(P x, P y) { return x.x * y.y - x.y * y.x; }

inline vector<P> Bag(vector<P> a) {
  sort(a.begin(), a.end(), [](auto x, auto y) { return x.x != y.x ? x.x < y.x : x.y < y.y; });
  vector<P> bag;
  rep (i, 0, a.size() - 1) {
    while (bag.size() >= 2 && ((bag.back() - bag[bag.size() - 2]) ^ (a[i] - bag.back())) <= 0)
      bag.pop_back();
    bag.push_back(a[i]);
  }
  // dbg(bag);
  int tmp = bag.size();
  per (i, a.size() - 2, 0) {
    while ((int)bag.size() > tmp && ((bag.back() - bag[bag.size() - 2]) ^ (a[i] - bag.back())) <= 0)
      bag.pop_back();
    bag.push_back(a[i]);
    // dbg(bag);
  }
  bag.pop_back();
  return bag;
}

int n;
vector<P> a;

inline P Rot(P x) { return {-x.y, x.x}; }

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  re (i, n) {
    double x, y;
    cin >> x >> y;
    a.push_back({x, y});
  }
  a = Bag(a);
  int n = a.size();
  // rep (i, 0, n - 1) cerr << a[i].x << ' ' << a[i].y << '\n';
  int u = 2;
  double ans = -1e18;
  rep (i, 0, n - 1) {
    auto Calc2 = [&](int x) {
      x %= n;
      return max((a[x] - a[i]).Norm2(), (a[x] - a[(i + 1) % n]).Norm2());
    };
    while (Calc2(u + 1) > Calc2(u)) ++u;
    double res = Calc2(u);
    // dbg(u, res);
    up(ans, res);
  }
  // dbg(ans);
  cout << fixed << setprecision(10);
  cout << sqrt(ans) << '\n';
  return 0;
}