QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403970 | #2433. Panda Preserve | u2x1 | AC ✓ | 707ms | 4260kb | C++20 | 4.0kb | 2024-05-03 00:28:07 | 2024-05-03 00:28:07 |
Judging History
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