QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403970#2433. Panda Preserveu2x1AC ✓707ms4260kbC++204.0kb2024-05-03 00:28:072024-05-03 00:28:07

Judging History

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

  • [2024-05-03 00:28:07]
  • 评测
  • 测评结果:AC
  • 用时:707ms
  • 内存:4260kb
  • [2024-05-03 00:28:07]
  • 提交

answer

#include "bits/stdc++.h"

#define all(x)   x.begin(), x.end()
#define NL       std::cout << '\n'

using lnt = long long;

const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 62;


using db = double; const db eps = 1e-4;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }

struct Pt { db x, y; };
std::istream& operator>>(std::istream& is, Pt &p) {
  int x, y; std::cin >> x >> y;
  p.x = x; p.y = y; return is;
}

Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator!=(Pt a, Pt b) { return sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
db dis2(Pt a, Pt b) { return dot(a-b, a-b); }
db dis(Pt a, Pt b) { return std::sqrt((long double)dis2(a, b)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
Pt rot90(Pt a) { return {-a.y, a.x}; }

struct Line { Pt s, t; };

Pt intersect(Line a, Line b) {
  db v = det(a.t - a.s, b.s - a.s);
  db u = det(a.t - a.s, b.t - a.s);
  return (b.s * u - b.t * v) / (u - v);
}

bool para(Line a, Line b) {
  return !sgn(det(a.t - a.s, b.t - b.s));
}

struct Seg { Pt s, t; };

Line bisector(Seg v) {
  Pt a = v.s + ((v.t - v.s) / 2);
  Pt b = a + rot90(v.t - v.s);
  return {a, b};
}

bool ptonseg(Pt x, Seg v) {
  return sgn(det(v.s - x, v.t - x)) == 0
      && sgn(dot(v.s - x, v.t - x)) <= 0;
}

std::vector<Pt> polyCut(std::vector<Pt> &v, Line l) {
  std::vector<Pt> ret; ret.reserve(v.size());
  for (int j = 0, i = v.size() - 1, ok = 0; j < v.size(); i = j++) {
    bool s = side(l.s, l.t, v[j]) > 0;
    if (s != side(l.s, l.t, v[i]) > 0) {
      ret.emplace_back(intersect(l, {v[i], v[j]}));
    }
    if (s) {
      ret.emplace_back(v[j]);
    }
  }
  return ret;
}


std::vector<std::vector<Pt>> voronoi(const std::vector<Pt> &p) {
  auto pp = p;
  std::shuffle(all(pp), std::mt19937(233333333));
  const db W = 3e4;
  std::vector<std::vector<Pt>> ret(p.size(),
    {{-W, -W}, {W, -W}, {W, W}, {-W, W}});
  for (int i = 0; i < p.size(); ++i) {
    for (auto u : pp) {
      if (u == p[i]) { continue; }
      ret[i] = polyCut(ret[i], bisector({p[i], u}));
    }
  }
  return ret;
}

bool inPoly(std::vector<Pt> &v, Pt p) {
  int cnt = 0;
  for (int i = v.size() - 1, j = 0; j < v.size(); i = j++) {
    if (ptonseg(p, {v[i], v[j]})) { return true; }
    int x = sgn(det(p - v[i], v[j] - v[i]));
    int y = sgn(v[i].y - p.y);
    int z = sgn(v[j].y - p.y);
    if (x > 0 && y <= 0 && z > 0) { ++cnt; }
    if (x < 0 && z <= 0 && y > 0) { --cnt; }
  }
  return cnt != 0;
}

bool seginter(Seg a, Seg b) {
  if (sgn(det(b.s-a.s, a.t-a.s)) * sgn(det(b.t-a.s, a.t-a.s)) == -1
   && sgn(det(a.s-b.s, b.t-b.s)) * sgn(det(a.t-b.s, b.t-b.s)) == -1) {
    return true;
  }
  return false;
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int n; std::cin >> n;
  std::vector<Pt> v(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> v[i];
  }


  db ret = 0;
  auto vg = voronoi(v);
  for (int i = 0; i < n; ++i) {
    const auto &vgp = vg[i];
    for (int a = vgp.size() - 1, b = 0; b < vgp.size(); a = b++) {
      if (inPoly(v, vgp[a])) {
        ret = std::max(dis2(v[i], vgp[a]), ret);
      }
      for (int c = v.size() - 1, d = 0; d < v.size(); c = d++) {
        if (para({vgp[a], vgp[b]}, {v[c], v[d]})) { continue; }
        if (seginter({vgp[a], vgp[b]}, {v[c], v[d]})) {
          Pt inter = intersect({vgp[a], vgp[b]}, {v[c], v[d]});
          db mi = linf;
          for (auto b : v) {
            mi = std::min(mi, dis2(inter, b));
          }
          ret = std::max(mi, ret);
        }
      }
    }
  }
  std::cout << std::fixed << std::setprecision(10);
  std::cout << std::sqrt(ret);
  return 0;
}




详细

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

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

Test #32:

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

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

score: 0
Accepted
time: 21ms
memory: 3912kb

Test #54:

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

Test #55:

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

Test #56:

score: 0
Accepted
time: 27ms
memory: 3932kb

Test #57:

score: 0
Accepted
time: 124ms
memory: 4048kb

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

score: 0
Accepted
time: 99ms
memory: 3844kb

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

score: 0
Accepted
time: 304ms
memory: 4188kb

Test #69:

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

Test #70:

score: 0
Accepted
time: 310ms
memory: 3996kb

Test #71:

score: 0
Accepted
time: 21ms
memory: 3792kb

Test #72:

score: 0
Accepted
time: 280ms
memory: 4132kb

Test #73:

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

Test #74:

score: 0
Accepted
time: 314ms
memory: 4172kb

Test #75:

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

Test #76:

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

Test #77:

score: 0
Accepted
time: 4ms
memory: 3852kb

Test #78:

score: 0
Accepted
time: 5ms
memory: 3848kb

Test #79:

score: 0
Accepted
time: 5ms
memory: 3804kb

Test #80:

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

Test #81:

score: 0
Accepted
time: 5ms
memory: 3736kb

Test #82:

score: 0
Accepted
time: 5ms
memory: 3732kb

Test #83:

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

Test #84:

score: 0
Accepted
time: 5ms
memory: 3852kb

Test #85:

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

Test #86:

score: 0
Accepted
time: 4ms
memory: 3752kb

Test #87:

score: 0
Accepted
time: 4ms
memory: 3872kb

Test #88:

score: 0
Accepted
time: 4ms
memory: 3716kb

Test #89:

score: 0
Accepted
time: 5ms
memory: 3712kb

Test #90:

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

Test #91:

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

Test #92:

score: 0
Accepted
time: 350ms
memory: 4192kb

Test #93:

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

Test #94:

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

Test #95:

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

Test #96:

score: 0
Accepted
time: 4ms
memory: 3804kb

Test #97:

score: 0
Accepted
time: 4ms
memory: 3712kb

Test #98:

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

Test #99:

score: 0
Accepted
time: 635ms
memory: 4128kb

Test #100:

score: 0
Accepted
time: 576ms
memory: 4064kb

Test #101:

score: 0
Accepted
time: 579ms
memory: 4184kb

Test #102:

score: 0
Accepted
time: 555ms
memory: 4044kb

Test #103:

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

Test #104:

score: 0
Accepted
time: 588ms
memory: 4260kb