QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380850 | #2433. Panda Preserve | 8BQube# | AC ✓ | 2246ms | 4312kb | C++20 | 7.3kb | 2024-04-07 13:26:07 | 2024-04-07 13:26:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
#define double long double
typedef pair<double, double> pdd;
typedef pair<pll, pll> Line;
const double eps = 1e-8;
pll operator+(const pll &a, const pll &b) { return pll(a.X + b.X, a.Y + b.Y); }
pdd operator+(const pdd &a, const pdd &b) { return pdd(a.X + b.X, a.Y + b.Y); }
pll operator-(const pll &a, const pll &b) { return pll(a.X - b.X, a.Y - b.Y); }
pdd operator-(const pdd &a, const pdd &b) { return pdd(a.X - b.X, a.Y - b.Y); }
pll operator*(const pll &a, const ll &b) { return pll(a.X * b, a.Y * b); }
pdd operator*(const pdd &a, const double &b) { return pdd(a.X * b, a.Y * b); }
pll operator/(const pll &a, const ll &b) { return pll(a.X / b, a.Y / b); }
pdd operator/(const pll &a, const double &b) { return pdd(a.X / b, a.Y / b); }
pdd operator/(const pdd &a, const double &b) { return pdd(a.X / b, a.Y / b); }
template<class T>
T dot(const pair<T, T> &a, const pair<T, T> &b) { return a.X * b.X + a.Y * b.Y; }
__int128 Ldot(const pll &a, const pll &b) { return (__int128)a.X * b.X + (__int128)a.Y * b.Y; }
template<class T>
T abs2(const pair<T, T> &a) { return dot(a, a); }
template<class T>
double abs(const pair<T, T> &a) { return sqrt(dot(a, a)); }
ll cross(const pll &a, const pll &b) { return a.X * b.Y - a.Y * b.X; }
double cross(const pdd &a, const pdd &b) { return a.X * b.Y - a.Y * b.X; }
__int128 Lcross(const pll &a, const pll &b) { return (__int128)a.X * b.Y - (__int128)a.Y * b.X; }
int sign(const ll &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
int sign(const double &a) { return fabs(a) < eps ? 0 : a > 0 ? 1 : -1; }
int sign(const __int128 &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
int ori(const pll &a, const pll &b, const pll &c) { return sign(cross(b - a, c - a)); }
int ori(const pdd &a, const pdd &b, const pdd &c) { return sign(cross(b - a, c - a)); }
int Lori(const pll &a, const pll &b, const pll &c) { return sign(Lcross(b - a, c - a)); }
bool btw(pll p1, pll p2, pll p3) {
if (Lori(p1, p2, p3) != 0) return 0;
return sign(Ldot(p1 - p3, p2 - p3)) <= 0;
}
bool btw(pdd p1, pdd p2, pdd p3) {
if (ori(p1, p2, p3) != 0) return 0;
return sign(dot(p1 - p3, p2 - p3)) <= 0;
}
pll perp(pll p1) { return pll(-p1.Y, p1.X); }
bool seg_intersect(pll p1, pll p2, pll p3, pll p4) {
int a123 = Lori(p1, p2, p3);
int a124 = Lori(p1, p2, p4);
int a341 = Lori(p3, p4, p1);
int a342 = Lori(p3, p4, p2);
if (a123 == 0 && a124 == 0)
return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
bool seg_intersect(pdd p1, pdd p2, pdd p3, pdd p4) {
int a123 = ori(p1, p2, p3);
int a124 = ori(p1, p2, p4);
int a341 = ori(p3, p4, p1);
int a342 = ori(p3, p4, p2);
if (a123 == 0 && a124 == 0)
return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
pdd intersect(pdd p1, pdd p2, pdd p3, pdd p4) {
double a123 = cross(p2 - p1, p3 - p1);
double a124 = cross(p2 - p1, p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
}
pair<pll, ll> intersect(pll p1, pll p2, pll p3, pll p4) {
ll a123 = cross(p2 - p1, p3 - p1);
ll a124 = cross(p2 - p1, p4 - p1);
if (a123 - a124 < 0) return make_pair(p3 * a124 - p4 * a123, a124 - a123);
return make_pair(p4 * a123 - p3 * a124, a123 - a124);
}
int cmp(pll a, pll b, bool same = true) {
#define is_neg(k) (sign(k.Y) < 0 || (sign(k.Y) == 0 && sign(k.X) < 0))
int A = is_neg(a), B = is_neg(b);
if (A != B) return A < B;
if (sign(cross(a, b)) == 0)
return same ? abs2(a) < abs2(b) : -1;
return sign(cross(a, b)) > 0;
}
pll area_pair(Line a, Line b) {
return pll(cross(a.Y - a.X, b.X - a.X), cross(a.Y - a.X, b.Y - a.X));
}
bool isin(Line l0, Line l1, Line l2) {
auto [a02X, a02Y] = area_pair(l0, l2);
auto [a12X, a12Y] = area_pair(l1, l2);
if (a12X - a12Y < 0) a12X *= -1, a12Y *= -1;
return (__int128)a02Y * a12X - (__int128)a02X * a12Y > 0;
}
vector<Line> halfPlaneInter(vector<Line> arr) {
sort(ALL(arr), [&](Line a, Line b) -> int {
if (cmp(a.Y - a.X, b.Y - b.X, 0) != -1)
return cmp(a.Y - a.X, b.Y - b.X, 0);
return ori(a.X, a.Y, b.Y) < 0;
});
deque<Line> dq(1, arr[0]);
auto pop_back = [&](int t, Line p) {
while (SZ(dq) >= t && !isin(p, dq[SZ(dq) - 2], dq.back()))
dq.pop_back();
};
auto pop_front = [&](int t, Line p) {
while (SZ(dq) >= t && !isin(p, dq[0], dq[1]))
dq.pop_front();
};
for (auto p : arr)
if (cmp(dq.back().Y - dq.back().X, p.Y - p.X, 0) != -1)
pop_back(2, p), pop_front(2, p), dq.pb(p);
pop_back(3, dq[0]), pop_front(3, dq.back());
return vector<Line>(ALL(dq));
}
const ll INF = 1e18;
const ll C = 20000;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<pll> poly(n);
for (auto &[x, y] : poly)
cin >> x >> y;
for (auto &p : poly)
p = p * 2;
auto inpoly = [&](pll p, ll base) {
for (int i = 0; i < n; ++i)
if (btw(poly[i] * base, poly[(i + 1) % n] * base, p))
return 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += seg_intersect(p, p + pll(1, INF), poly[i] * base, poly[(i + 1) % n] * base);
}
return cnt & 1;
};
double ans = 0;
auto check = [&](pair<pll, ll> p, pll q) {
//cerr << "(b)check (" << p.X.X / (double)p.Y << ", " << p.X.Y / (double)p.Y << ")\n";
if (!inpoly(p.X, p.Y)) return;
pdd cur = p.X / (double)(p.Y);
//cerr << "check (" << cur.X << ", " << cur.Y << ")\n";
ans = max(ans, abs(cur - (pdd)q));
};
for (int i = 0; i < n; ++i) {
vector<Line> vec;
vec.pb(Line(pll(0, -C), pll(1, -C)));
vec.pb(Line(pll(C, 0), pll(C, 1)));
vec.pb(Line(pll(0, C), pll(-1, C)));
vec.pb(Line(pll(-C, 0), pll(-C, -1)));
for (int j = 0; j < n; ++j)
if (i != j) {
pll mid = poly[i] + poly[j];
mid = mid / 2LL;
vec.emplace_back(mid, mid + perp(poly[j] - poly[i]));
}
vec = halfPlaneInter(vec);
/*cerr << "(" << poly[i].X << ", " << poly[i].Y << "):\n";
for (auto [a, b] : vec)
cerr << "(" << a.X << ", " << a.Y << ")---(" << b.X << ", " << b.Y << ")\n";*/
vector<pair<pll, ll>> convex;
for (int j = 0; j < SZ(vec); ++j) {
convex.pb(intersect(vec[j].X, vec[j].Y, vec[(j + 1) % SZ(vec)].X, vec[(j + 1) % SZ(vec)].Y));
check(convex.back(), poly[i]);
}
for (int t = 0; t < SZ(convex); ++t) {
auto [p, b1] = convex[t];
auto [q, b2] = convex[(t + 1) % SZ(convex)];
pdd a = p / (double)(b1), b = q / (double)(b2);
for (int j = 0; j < n; ++j)
if (seg_intersect(a, b, (pdd)poly[j], (pdd)poly[(j + 1) % n])) {
pdd c = intersect(a, b, (pdd)poly[j], (pdd)poly[(j + 1) % n]);
ans = max(ans, abs(c - (pdd)poly[i]));
}
}
}
cout << fixed << setprecision(20) << ans / 2 << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3996kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3832kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3932kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3968kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 3932kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3840kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 4060kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 4000kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 3776kb
Test #17:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #18:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 3800kb
Test #20:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #21:
score: 0
Accepted
time: 0ms
memory: 3964kb
Test #22:
score: 0
Accepted
time: 1ms
memory: 3936kb
Test #23:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #24:
score: 0
Accepted
time: 1ms
memory: 3888kb
Test #25:
score: 0
Accepted
time: 0ms
memory: 3896kb
Test #26:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #27:
score: 0
Accepted
time: 1ms
memory: 4004kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #29:
score: 0
Accepted
time: 1ms
memory: 4076kb
Test #30:
score: 0
Accepted
time: 1ms
memory: 3968kb
Test #31:
score: 0
Accepted
time: 0ms
memory: 4000kb
Test #32:
score: 0
Accepted
time: 0ms
memory: 3820kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3964kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 4064kb
Test #36:
score: 0
Accepted
time: 1ms
memory: 3872kb
Test #37:
score: 0
Accepted
time: 1ms
memory: 3784kb
Test #38:
score: 0
Accepted
time: 1ms
memory: 3832kb
Test #39:
score: 0
Accepted
time: 0ms
memory: 3776kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #41:
score: 0
Accepted
time: 1ms
memory: 3900kb
Test #42:
score: 0
Accepted
time: 0ms
memory: 4080kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #44:
score: 0
Accepted
time: 1ms
memory: 3936kb
Test #45:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #46:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #47:
score: 0
Accepted
time: 1ms
memory: 3792kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 3856kb
Test #49:
score: 0
Accepted
time: 1ms
memory: 4064kb
Test #50:
score: 0
Accepted
time: 1ms
memory: 3892kb
Test #51:
score: 0
Accepted
time: 1ms
memory: 3900kb
Test #52:
score: 0
Accepted
time: 5ms
memory: 4072kb
Test #53:
score: 0
Accepted
time: 103ms
memory: 3904kb
Test #54:
score: 0
Accepted
time: 459ms
memory: 3956kb
Test #55:
score: 0
Accepted
time: 5ms
memory: 3908kb
Test #56:
score: 0
Accepted
time: 123ms
memory: 3904kb
Test #57:
score: 0
Accepted
time: 506ms
memory: 3948kb
Test #58:
score: 0
Accepted
time: 3ms
memory: 4012kb
Test #59:
score: 0
Accepted
time: 121ms
memory: 3892kb
Test #60:
score: 0
Accepted
time: 509ms
memory: 3952kb
Test #61:
score: 0
Accepted
time: 2ms
memory: 3884kb
Test #62:
score: 0
Accepted
time: 95ms
memory: 3904kb
Test #63:
score: 0
Accepted
time: 397ms
memory: 4208kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 4000kb
Test #65:
score: 0
Accepted
time: 1ms
memory: 4004kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3776kb
Test #67:
score: 0
Accepted
time: 0ms
memory: 3932kb
Test #68:
score: 0
Accepted
time: 1759ms
memory: 4184kb
Test #69:
score: 0
Accepted
time: 1ms
memory: 3776kb
Test #70:
score: 0
Accepted
time: 1877ms
memory: 4016kb
Test #71:
score: 0
Accepted
time: 103ms
memory: 3840kb
Test #72:
score: 0
Accepted
time: 1583ms
memory: 4168kb
Test #73:
score: 0
Accepted
time: 292ms
memory: 4116kb
Test #74:
score: 0
Accepted
time: 1568ms
memory: 3984kb
Test #75:
score: 0
Accepted
time: 344ms
memory: 4180kb
Test #76:
score: 0
Accepted
time: 14ms
memory: 4088kb
Test #77:
score: 0
Accepted
time: 11ms
memory: 4000kb
Test #78:
score: 0
Accepted
time: 14ms
memory: 3960kb
Test #79:
score: 0
Accepted
time: 15ms
memory: 3992kb
Test #80:
score: 0
Accepted
time: 16ms
memory: 3992kb
Test #81:
score: 0
Accepted
time: 13ms
memory: 4024kb
Test #82:
score: 0
Accepted
time: 16ms
memory: 3956kb
Test #83:
score: 0
Accepted
time: 17ms
memory: 3956kb
Test #84:
score: 0
Accepted
time: 15ms
memory: 3856kb
Test #85:
score: 0
Accepted
time: 16ms
memory: 4024kb
Test #86:
score: 0
Accepted
time: 15ms
memory: 3876kb
Test #87:
score: 0
Accepted
time: 15ms
memory: 3868kb
Test #88:
score: 0
Accepted
time: 16ms
memory: 3800kb
Test #89:
score: 0
Accepted
time: 15ms
memory: 4100kb
Test #90:
score: 0
Accepted
time: 15ms
memory: 3800kb
Test #91:
score: 0
Accepted
time: 16ms
memory: 3860kb
Test #92:
score: 0
Accepted
time: 1270ms
memory: 4312kb
Test #93:
score: 0
Accepted
time: 1216ms
memory: 4176kb
Test #94:
score: 0
Accepted
time: 4ms
memory: 4088kb
Test #95:
score: 0
Accepted
time: 5ms
memory: 3912kb
Test #96:
score: 0
Accepted
time: 14ms
memory: 4104kb
Test #97:
score: 0
Accepted
time: 13ms
memory: 4024kb
Test #98:
score: 0
Accepted
time: 2200ms
memory: 4240kb
Test #99:
score: 0
Accepted
time: 2236ms
memory: 4012kb
Test #100:
score: 0
Accepted
time: 2246ms
memory: 4000kb
Test #101:
score: 0
Accepted
time: 2235ms
memory: 3988kb
Test #102:
score: 0
Accepted
time: 2194ms
memory: 4000kb
Test #103:
score: 0
Accepted
time: 2001ms
memory: 4100kb
Test #104:
score: 0
Accepted
time: 1991ms
memory: 4000kb