QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380851 | #2433. Panda Preserve | ckiseki# | AC ✓ | 4601ms | 4456kb | C++20 | 6.0kb | 2024-04-07 13:27:44 | 2024-04-07 13:27:45 |
Judging History
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;
}
Details
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