QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380851#2433. Panda Preserveckiseki#AC ✓4601ms4456kbC++206.0kb2024-04-07 13:27:442024-04-07 13:27:45

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 13:27:45]
  • 评测
  • 测评结果:AC
  • 用时:4601ms
  • 内存:4456kb
  • [2024-04-07 13:27:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using i128 = __int128_t;

#define RE real
#define IM imag

using llf = long double;
using lld = int64_t;
using PT = complex<lld>;
using P = PT;
using PF = complex<llf>;

int sgn(int x) { return (x > 0) - (x < 0); }
int sgn(lld x) { return (x > 0) - (x < 0); }
int sgn(i128 x) { return (x > 0) - (x < 0); }

PF toPF(PT p) { return PF{RE(p), IM(p)}; }

lld cross(P a, P b) { return IM(conj(a) * b); }

P rot90(P p) { return P{-IM(p), RE(p)}; }

int ori(P a, P b, P c) {
  return sgn(cross(b - a, c - a));
}

const llf eps = 1e-9;
int sgn(llf x) { return (x > eps) - (x < -eps); }
llf cross(PF a, PF b) { return IM(conj(a) * b); }
llf dot(PF a, PF b) { return RE(conj(a) * b); }
int ori(PF a, PF b, PF c) {
  return sgn(cross(b - a, c - a));
}

int quad(P p) {
  return (IM(p) == 0) ? (RE(p) < 0 ? 3 : 1) : (IM(p) < 0 ? 0 : 2);
}
int argCmp(P a, P b) {
  int qa = quad(a), qb = quad(b);
  if (qa != qb) return sgn(qa - qb);
  return sgn(cross(b, a));
}

template <typename V> llf area(const V &pt) {
  lld ret = 0;
  for (int i = 1; i + 1 < (int)pt.size(); i++)
    ret += cross(pt[i] - pt[0], pt[i + 1] - pt[0]);
  return ret / 2.0;
}

struct Line {
  P st, ed, dir;
  Line(P s, P e) : st(s), ed(e), dir(e - s) {}
};
using LN = const Line &;
PF intersect(LN A, LN B) {
  llf t = cross(B.st - A.st, B.dir) / llf(cross(A.dir, B.dir));
  return toPF(A.st) + toPF(A.dir) * t;
}
bool cov(LN l, LN A, LN B) {
  i128 u = cross(B.st - A.st, B.dir);
  i128 v = cross(A.dir, B.dir);
  i128 x = RE(A.dir) * u + RE(A.st - l.st) * v;
  i128 y = IM(A.dir) * u + IM(A.st - l.st) * v;
  return sgn(x * IM(l.dir) - y * RE(l.dir)) * sgn(v) >= 0;
}
bool operator<(LN a, LN b) {
  if (int c = argCmp(a.dir, b.dir)) return c == -1;
  return ori(a.st, a.ed, b.st) < 0;
}

vector<PF> HPI(vector<Line> &q) {
  sort(q.begin(), q.end());
  int n = (int)q.size(), l = 0, r = -1;
  for (int i = 0; i < n; i++ ) {
    if (i && !argCmp(q[i].dir, q[i - 1].dir)) continue;
    while (l < r && cov(q[i], q[r - 1], q[r])) --r;
    while (l < r && cov(q[i], q[l], q[l + 1])) ++l;
    q[++r] = q[i];
  }
  while (l < r && cov(q[l], q[r - 1], q[r])) --r;
  while (l < r && cov(q[r], q[l], q[l + 1])) ++l;
  n = r - l + 1;
  if (n <= 2 || !argCmp(q[l].dir, q[r].dir)) {
    q.clear();
    return {};
  }
  vector<PF> pt(n);
  for (int i = 0; i < n; i++)
    pt[i] = intersect(q[i + l], q[(i + 1) % n + l]);
  q = vector(q.begin() + l, q.begin() + r + 1);
  return pt;
}

struct Seg {
  PF st, dir;
  Seg(PF s, PF e) : st(s), dir(e - s) {}
  static bool valid(llf p, llf q) {
    if (q < 0) q = -q, p = -p;
    return sgn(0 - p) <= 0 && sgn(p - q) <= 0;
    // return 0 <= p && p <= q;
  }
  vector<PF> ends() const { return {st, st + dir}; }
};

template <typename T> bool isInter(T A, PF p) {
  if (abs(A.dir) < eps) return abs(p - A.st) < eps;
  return sgn(cross(p - A.st, A.dir)) == 0 && T::valid(dot(p - A.st, A.dir), norm(A.dir));
}

template <typename U, typename V>
bool isInter(U A, V B) {
  if (sgn(cross(A.dir, B.dir)) == 0) {
    bool res = false;
    for (PF p : A.ends()) res |= isInter(B, p);
    for (PF p : B.ends()) res |= isInter(A, p);
    return res;
  }
  PF D = B.st - A.st;
  llf C = cross(A.dir, B.dir);
  return U::valid(cross(D, B.dir), C) && V::valid(cross(D, A.dir), C);
}

bool PIP(const vector<PF> &p, PF z, bool strict = true) {
  int cnt = 0, n = (int)p.size();
  for (int i = 0; i < n; i++) {
    PF A = p[i], B = p[(i + 1) % n];
    if (isInter(Seg(A, B), z)) return !strict;
    auto zy = IM(z), Ay = IM(A), By = IM(B);
    cnt ^= ((zy < Ay) - (zy < By)) * ori(z, A, B) > 0;
  }
  return cnt;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin >> n;

  vector<P> p(n);
  vector<PF> pf(n);

  vector<Seg> ps;
  vector<Line> pe;

  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    p[i] = P(x, y);

    pf[i] = toPF(p[i]);
  }

  for (int i = 0; i < n; i++)
    ps.emplace_back(pf[i], pf[(i + 1) % n]);
  for (int i = 0; i < n; i++)
    pe.emplace_back(p[i] * lld(2), p[(i + 1) % n] * lld(2));

  vector<Line> frame;
  {
    const int C = 20005;
    P q[4] = {P(-C, -C), P(C, -C), P(C, C), P(-C, C)};
    frame = {Line(q[0], q[1]), Line(q[1], q[2]), Line(q[2], q[3]), Line(q[3], q[0])};
  }

  llf ans = 0;

  for (int i = 0; i < n; i++) {
    vector<Line> ls = frame;
    for (int j = 0; j < n; j++) if (j != i) {
      P m = p[i] + p[j], d = rot90(p[j] - p[i]);
      assert(norm(d) != 0);
      ls.emplace_back(m, m + d);
    }

    auto hull = HPI(ls);
    if (hull.empty())
      continue;

    for (PF &z : hull)
      z /= llf(2);

    for (size_t j = 0; j < hull.size(); j++) {
      if (PIP(pf, hull[j], false)) {
        ans = max(ans, abs(hull[j] - pf[i]));
      }
    }

    for (size_t j = 0; j < pf.size(); j++) {
      if (PIP(hull, pf[j], false)) {
        ans = max(ans, abs(pf[j] - pf[i]));
      }
    }

    vector<Seg> seg;
    for (size_t j = 0; j < hull.size(); j++)
      seg.emplace_back(hull[(j + hull.size() - 1) % hull.size()], hull[j]);

    for (size_t j = 0; j < seg.size(); j++) {
      for (size_t k = 0; k < ps.size(); k++) {
        if (isInter(seg[j], ps[k])) {
          debug(seg[j].dir, ps[k].dir);
          debug(ls[j].dir, pe[k].dir);
          PF z = intersect(ls[j], pe[k]);
          z /= llf(2);
          ans = max(ans, abs(z - pf[i]));
        }
      }
    }
  }

  cout << fixed << setprecision(20);
  cout << ans << '\n';

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3948kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3948kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #6:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3860kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3972kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 4028kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #13:

score: 0
Accepted
time: 0ms
memory: 3948kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #16:

score: 0
Accepted
time: 0ms
memory: 3924kb

Test #17:

score: 0
Accepted
time: 0ms
memory: 3908kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 3960kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 4024kb

Test #20:

score: 0
Accepted
time: 0ms
memory: 3900kb

Test #21:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #22:

score: 0
Accepted
time: 0ms
memory: 4028kb

Test #23:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #24:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #25:

score: 0
Accepted
time: 0ms
memory: 3960kb

Test #26:

score: 0
Accepted
time: 1ms
memory: 3984kb

Test #27:

score: 0
Accepted
time: 1ms
memory: 3976kb

Test #28:

score: 0
Accepted
time: 0ms
memory: 3880kb

Test #29:

score: 0
Accepted
time: 1ms
memory: 3960kb

Test #30:

score: 0
Accepted
time: 0ms
memory: 3952kb

Test #31:

score: 0
Accepted
time: 0ms
memory: 3952kb

Test #32:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #33:

score: 0
Accepted
time: 1ms
memory: 4036kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3868kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3960kb

Test #36:

score: 0
Accepted
time: 1ms
memory: 3964kb

Test #37:

score: 0
Accepted
time: 1ms
memory: 3964kb

Test #38:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #39:

score: 0
Accepted
time: 0ms
memory: 3868kb

Test #40:

score: 0
Accepted
time: 1ms
memory: 3908kb

Test #41:

score: 0
Accepted
time: 1ms
memory: 3964kb

Test #42:

score: 0
Accepted
time: 0ms
memory: 3924kb

Test #43:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #44:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #45:

score: 0
Accepted
time: 0ms
memory: 3924kb

Test #46:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #47:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #48:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #49:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #50:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #51:

score: 0
Accepted
time: 0ms
memory: 3972kb

Test #52:

score: 0
Accepted
time: 9ms
memory: 3928kb

Test #53:

score: 0
Accepted
time: 214ms
memory: 4080kb

Test #54:

score: 0
Accepted
time: 880ms
memory: 4056kb

Test #55:

score: 0
Accepted
time: 11ms
memory: 3992kb

Test #56:

score: 0
Accepted
time: 264ms
memory: 4112kb

Test #57:

score: 0
Accepted
time: 1100ms
memory: 4160kb

Test #58:

score: 0
Accepted
time: 11ms
memory: 3992kb

Test #59:

score: 0
Accepted
time: 266ms
memory: 4088kb

Test #60:

score: 0
Accepted
time: 1103ms
memory: 4120kb

Test #61:

score: 0
Accepted
time: 10ms
memory: 3976kb

Test #62:

score: 0
Accepted
time: 238ms
memory: 4160kb

Test #63:

score: 0
Accepted
time: 978ms
memory: 4208kb

Test #64:

score: 0
Accepted
time: 0ms
memory: 3856kb

Test #65:

score: 0
Accepted
time: 0ms
memory: 3936kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #67:

score: 0
Accepted
time: 0ms
memory: 3944kb

Test #68:

score: 0
Accepted
time: 4458ms
memory: 4348kb

Test #69:

score: 0
Accepted
time: 0ms
memory: 3888kb

Test #70:

score: 0
Accepted
time: 4449ms
memory: 4452kb

Test #71:

score: 0
Accepted
time: 210ms
memory: 4160kb

Test #72:

score: 0
Accepted
time: 4140ms
memory: 4376kb

Test #73:

score: 0
Accepted
time: 590ms
memory: 4112kb

Test #74:

score: 0
Accepted
time: 4104ms
memory: 4332kb

Test #75:

score: 0
Accepted
time: 1025ms
memory: 4116kb

Test #76:

score: 0
Accepted
time: 35ms
memory: 3892kb

Test #77:

score: 0
Accepted
time: 31ms
memory: 4092kb

Test #78:

score: 0
Accepted
time: 35ms
memory: 3952kb

Test #79:

score: 0
Accepted
time: 35ms
memory: 3964kb

Test #80:

score: 0
Accepted
time: 38ms
memory: 4028kb

Test #81:

score: 0
Accepted
time: 38ms
memory: 3936kb

Test #82:

score: 0
Accepted
time: 39ms
memory: 4016kb

Test #83:

score: 0
Accepted
time: 38ms
memory: 4096kb

Test #84:

score: 0
Accepted
time: 36ms
memory: 4020kb

Test #85:

score: 0
Accepted
time: 36ms
memory: 4020kb

Test #86:

score: 0
Accepted
time: 33ms
memory: 3924kb

Test #87:

score: 0
Accepted
time: 33ms
memory: 4100kb

Test #88:

score: 0
Accepted
time: 37ms
memory: 4084kb

Test #89:

score: 0
Accepted
time: 37ms
memory: 4084kb

Test #90:

score: 0
Accepted
time: 37ms
memory: 4036kb

Test #91:

score: 0
Accepted
time: 38ms
memory: 3924kb

Test #92:

score: 0
Accepted
time: 3205ms
memory: 4292kb

Test #93:

score: 0
Accepted
time: 3037ms
memory: 4292kb

Test #94:

score: 0
Accepted
time: 2ms
memory: 4012kb

Test #95:

score: 0
Accepted
time: 10ms
memory: 3980kb

Test #96:

score: 0
Accepted
time: 30ms
memory: 3988kb

Test #97:

score: 0
Accepted
time: 30ms
memory: 4092kb

Test #98:

score: 0
Accepted
time: 4515ms
memory: 4304kb

Test #99:

score: 0
Accepted
time: 4399ms
memory: 4392kb

Test #100:

score: 0
Accepted
time: 4601ms
memory: 4304kb

Test #101:

score: 0
Accepted
time: 4554ms
memory: 4376kb

Test #102:

score: 0
Accepted
time: 4490ms
memory: 4328kb

Test #103:

score: 0
Accepted
time: 3957ms
memory: 4456kb

Test #104:

score: 0
Accepted
time: 4022ms
memory: 4292kb