QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71788 | #2433. Panda Preserve | He_Ren | AC ✓ | 1772ms | 4180kb | C++14 | 6.0kb | 2023-01-12 01:14:03 | 2023-01-12 01:14:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
const int MAXN = 2e3 + 5;
const ldb eps = 1e-9;
const ldb pi = acosl(-1);
mt19937 rnd((unsigned long long)new char ^time(0));
uniform_real_distribution<ldb> rndang(-pi, pi);
inline int sgn(ldb x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
struct Vector {
ldb x, y;
Vector(void) {}
Vector(ldb _x, ldb _y): x(_x), y(_y) {}
inline ldb len(void) const {
return sqrtl(x * x + y * y);
}
inline ldb ang(void) const {
return atan2l(y, x);
}
};
Vector operator + (const Vector &p, const Vector &q) {
return Vector(p.x + q.x, p.y + q.y);
}
Vector operator - (const Vector &p, const Vector &q) {
return Vector(p.x - q.x, p.y - q.y);
}
Vector operator - (const Vector &p) {
return Vector(-p.x, -p.y);
}
Vector operator * (const Vector &p, ldb k) {
return Vector(p.x * k, p.y * k);
}
Vector operator / (const Vector &p, ldb k) {
return Vector(p.x / k, p.y / k);
}
ldb cross(const Vector &p, const Vector &q) {
return p.x * q.y - p.y * q.x;
}
ldb dot(const Vector &p, const Vector &q) {
return p.x * q.x + p.y * q.y;
}
ldb dist(const Vector &p, const Vector &q) {
return (p - q).len();
}
Vector rotate(const Vector &v, ldb tcos, ldb tsin) {
return Vector(v.x * tcos - v.y * tsin, v.x * tsin + v.y * tcos);
}
Vector rotate(const Vector &v, ldb ang) {
return rotate(v, cosl(ang), sinl(ang));
}
struct Line {
Vector o, v;
Line(void) {}
Line(const Vector &_o, const Vector &_v): o(_o), v(_v) {}
bool con(const Vector &p) const {
return sgn(cross(p - o, v)) == 0;
}
};
struct Seg {
Vector a, b;
Seg(void) {}
Seg(const Vector &_a, const Vector &_b): a(_a), b(_b) {}
operator Line(void) const {
return Line(a, b - a);
}
bool con(const Vector &p) const {
return sgn(cross(p - a, b - a)) == 0 && sgn(dot(p - a, b - a)) >= 0 && sgn(dot(p - b, a - b)) >= 0;
}
bool _twoside(const Seg &oth) const {
int x = sgn(cross(oth.a - b, a - b));
if (x == 0)
return 1;
int y = sgn(cross(oth.b - b, a - b));
if (y == 0)
return 1;
return x != y;
}
};
Line make_Line(const Vector &p, const Vector &q) {
return Line(p, q - p);
}
pair<Vector, bool> inter(const Line &a, const Line &b) {
ldb k = cross(a.v, b.v);
if (!sgn(k))
return {a.o, 0};
return {a.o + a.v *(cross(b.o - a.o, b.v) / k), 1};
}
bool hasinter(const Seg &a, const Seg &b) {
return a._twoside(b) && b._twoside(a);
}
pair<Vector, bool> inter(const Seg &a, const Seg &b) {
if (!hasinter(a, b))
return {a.a, 0};
else
return inter(Line(a), Line(b));
}
struct Halfplane: Line {
ldb ang;
Halfplane(void) {}
Halfplane(const Line &_a, const ldb _ang): Line(_a), ang(_ang) {}
Halfplane(const Line &_a): Line(_a), ang(v.ang()) {}
int con(const Vector &p) const {
return sgn(cross(v, p - o));
}
bool operator < (const Halfplane &oth) const {
if (sgn(ang - oth.ang) != 0)
return ang < oth.ang;
else
return oth.con(o) > 0;
}
};
vector<Vector> hp_intersection(vector<Halfplane> h) {
Vector base[] = {Vector(-1e5, -1e5), Vector(1e5, -1e5), Vector(1e5, 1e5), Vector(-1e5, 1e5)};
for (int i = 0; i < 4; ++i)
h.emplace_back(make_Line(base[i], base[(i + 1) & 3]));
vector<Halfplane> q(h.size());
vector<Vector> qq(h.size());
int hd = 0, tl = -1;
sort(h.begin(), h.end());
for (int i = 0; i < (int)h.size(); ++i)
if (i == 0 || sgn(h[i].ang - h[i - 1].ang) != 0) {
while (tl - hd + 1 >= 2 && h[i].con(qq[tl - 1]) <= 0)
--tl;
while (tl - hd + 1 >= 2 && h[i].con(qq[hd]) <= 0)
++hd;
if (hd <= tl)
qq[tl] = inter(h[i], q[tl]).first;
q[++tl] = h[i];
}
while (tl - hd + 1 >= 3 && q[hd].con(qq[tl - 1]) <= 0)
--tl;
if (tl - hd + 1 < 3)
return {};
qq[tl] = inter(q[hd], q[tl]).first;
qq.erase(qq.begin(), qq.begin() + hd);
qq.resize(tl - hd + 1);
return qq;
}
Vector p[MAXN];
int main(void) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
p[i] = Vector(x, y);
}
p[0] = p[n];
p[n + 1] = p[1];
static Seg seg[MAXN];
for (int i = 1; i <= n; ++i)
seg[i] = Seg(p[i], p[i + 1]);
auto con = [&](Vector o) -> bool {
for (int i = 1; i <= n; ++i)
if (seg[i].con(o))
return 1;
Vector v(0, 1e6);
v = rotate(v, rndang(rnd));
Seg l(o, o + v);
int res = 0;
for (int i = 1; i <= n; ++i)
res ^= hasinter(l, seg[i]);
return res;
};
ldb ans = 0;
for (int rt = 1; rt <= n; ++rt) {
vector<Halfplane> vec;
for (int i = 1; i <= n; ++i)
if (i != rt) {
auto o = (p[i] + p[rt]) / 2, v = p[rt] - p[i];
swap(v.x, v.y);
v.y *= -1;
vec.emplace_back(Line(o, v));
}
auto h = hp_intersection(vec);
vector<Seg> hl(h.size());
for (int i = 0; i < (int)h.size(); ++i)
hl[i] = Seg(h[i], h[(i + 1) % (int)h.size()]);
for (auto t : h)
if (con(t))
ans = max(ans, dist(t, p[rt]));
for (int i = 1; i <= n; ++i)
for (auto l : hl) {
Vector cur;
bool ok;
tie(cur, ok) = inter(seg[i], l);
if (ok)
ans = max(ans, dist(cur, p[rt]));
}
}
printf("%.20lf", (double)ans);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 2ms
memory: 3736kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 3736kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 3680kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3772kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3728kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 3680kb
Test #8:
score: 0
Accepted
time: 2ms
memory: 3768kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 3796kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 3728kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 3796kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 3768kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #14:
score: 0
Accepted
time: 2ms
memory: 3724kb
Test #15:
score: 0
Accepted
time: 2ms
memory: 3688kb
Test #16:
score: 0
Accepted
time: 2ms
memory: 3728kb
Test #17:
score: 0
Accepted
time: 1ms
memory: 3804kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 3732kb
Test #19:
score: 0
Accepted
time: 2ms
memory: 3684kb
Test #20:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
Test #22:
score: 0
Accepted
time: 2ms
memory: 3852kb
Test #23:
score: 0
Accepted
time: 3ms
memory: 3708kb
Test #24:
score: 0
Accepted
time: 2ms
memory: 3832kb
Test #25:
score: 0
Accepted
time: 2ms
memory: 3804kb
Test #26:
score: 0
Accepted
time: 0ms
memory: 3852kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3804kb
Test #28:
score: 0
Accepted
time: 2ms
memory: 3752kb
Test #29:
score: 0
Accepted
time: 2ms
memory: 3756kb
Test #30:
score: 0
Accepted
time: 0ms
memory: 3732kb
Test #31:
score: 0
Accepted
time: 2ms
memory: 3756kb
Test #32:
score: 0
Accepted
time: 0ms
memory: 3804kb
Test #33:
score: 0
Accepted
time: 2ms
memory: 3864kb
Test #34:
score: 0
Accepted
time: 2ms
memory: 3804kb
Test #35:
score: 0
Accepted
time: 2ms
memory: 3736kb
Test #36:
score: 0
Accepted
time: 2ms
memory: 3692kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #38:
score: 0
Accepted
time: 2ms
memory: 3768kb
Test #39:
score: 0
Accepted
time: 2ms
memory: 3840kb
Test #40:
score: 0
Accepted
time: 2ms
memory: 3784kb
Test #41:
score: 0
Accepted
time: 2ms
memory: 3856kb
Test #42:
score: 0
Accepted
time: 2ms
memory: 3680kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 3840kb
Test #44:
score: 0
Accepted
time: 2ms
memory: 3732kb
Test #45:
score: 0
Accepted
time: 2ms
memory: 3736kb
Test #46:
score: 0
Accepted
time: 0ms
memory: 3732kb
Test #47:
score: 0
Accepted
time: 2ms
memory: 3852kb
Test #48:
score: 0
Accepted
time: 2ms
memory: 3720kb
Test #49:
score: 0
Accepted
time: 2ms
memory: 3796kb
Test #50:
score: 0
Accepted
time: 2ms
memory: 3840kb
Test #51:
score: 0
Accepted
time: 2ms
memory: 3788kb
Test #52:
score: 0
Accepted
time: 5ms
memory: 3768kb
Test #53:
score: 0
Accepted
time: 89ms
memory: 3888kb
Test #54:
score: 0
Accepted
time: 367ms
memory: 4016kb
Test #55:
score: 0
Accepted
time: 6ms
memory: 3896kb
Test #56:
score: 0
Accepted
time: 123ms
memory: 3912kb
Test #57:
score: 0
Accepted
time: 392ms
memory: 3972kb
Test #58:
score: 0
Accepted
time: 6ms
memory: 3720kb
Test #59:
score: 0
Accepted
time: 106ms
memory: 4024kb
Test #60:
score: 0
Accepted
time: 456ms
memory: 3988kb
Test #61:
score: 0
Accepted
time: 5ms
memory: 3836kb
Test #62:
score: 0
Accepted
time: 94ms
memory: 3956kb
Test #63:
score: 0
Accepted
time: 359ms
memory: 4016kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 3732kb
Test #65:
score: 0
Accepted
time: 2ms
memory: 3728kb
Test #66:
score: 0
Accepted
time: 2ms
memory: 3848kb
Test #67:
score: 0
Accepted
time: 1ms
memory: 3728kb
Test #68:
score: 0
Accepted
time: 1567ms
memory: 4108kb
Test #69:
score: 0
Accepted
time: 2ms
memory: 3844kb
Test #70:
score: 0
Accepted
time: 1522ms
memory: 4068kb
Test #71:
score: 0
Accepted
time: 94ms
memory: 4020kb
Test #72:
score: 0
Accepted
time: 1291ms
memory: 4136kb
Test #73:
score: 0
Accepted
time: 327ms
memory: 3992kb
Test #74:
score: 0
Accepted
time: 1524ms
memory: 4180kb
Test #75:
score: 0
Accepted
time: 314ms
memory: 3980kb
Test #76:
score: 0
Accepted
time: 13ms
memory: 3780kb
Test #77:
score: 0
Accepted
time: 8ms
memory: 3844kb
Test #78:
score: 0
Accepted
time: 13ms
memory: 3860kb
Test #79:
score: 0
Accepted
time: 13ms
memory: 3844kb
Test #80:
score: 0
Accepted
time: 10ms
memory: 3848kb
Test #81:
score: 0
Accepted
time: 10ms
memory: 3816kb
Test #82:
score: 0
Accepted
time: 10ms
memory: 3812kb
Test #83:
score: 0
Accepted
time: 11ms
memory: 3808kb
Test #84:
score: 0
Accepted
time: 13ms
memory: 3800kb
Test #85:
score: 0
Accepted
time: 10ms
memory: 3908kb
Test #86:
score: 0
Accepted
time: 10ms
memory: 3908kb
Test #87:
score: 0
Accepted
time: 13ms
memory: 3804kb
Test #88:
score: 0
Accepted
time: 14ms
memory: 3804kb
Test #89:
score: 0
Accepted
time: 14ms
memory: 3920kb
Test #90:
score: 0
Accepted
time: 14ms
memory: 3824kb
Test #91:
score: 0
Accepted
time: 19ms
memory: 3812kb
Test #92:
score: 0
Accepted
time: 1215ms
memory: 4088kb
Test #93:
score: 0
Accepted
time: 1235ms
memory: 4036kb
Test #94:
score: 0
Accepted
time: 7ms
memory: 3868kb
Test #95:
score: 0
Accepted
time: 5ms
memory: 3840kb
Test #96:
score: 0
Accepted
time: 9ms
memory: 3844kb
Test #97:
score: 0
Accepted
time: 6ms
memory: 3760kb
Test #98:
score: 0
Accepted
time: 1697ms
memory: 4024kb
Test #99:
score: 0
Accepted
time: 1762ms
memory: 3992kb
Test #100:
score: 0
Accepted
time: 1720ms
memory: 4064kb
Test #101:
score: 0
Accepted
time: 1772ms
memory: 3992kb
Test #102:
score: 0
Accepted
time: 1692ms
memory: 4096kb
Test #103:
score: 0
Accepted
time: 1604ms
memory: 4036kb
Test #104:
score: 0
Accepted
time: 1724ms
memory: 4112kb