QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334144 | #2433. Panda Preserve | neko_nyaa | AC ✓ | 2880ms | 6740kb | C++23 | 6.7kb | 2024-02-21 11:09:30 | 2024-02-21 11:09:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << " " << p.y << ")"; }
};
typedef Point<double> P;
typedef struct Quad* Q;
typedef __int128_t lll; // (can be ll if coords are < 2e4)
P arb(LLONG_MAX,LLONG_MAX); // not equal to any other point
struct Quad {
bool mark; Q o, rot; P p;
P F() { return r()->p; }
Q r() { return rot->rot; }
Q prev() { return rot->o->rot; }
Q next() { return r()->prev(); }
};
bool circ(P p, P a, P b, P c) { // is p in the circumcircle?
lll p2 = p.dist2(), A = a.dist2()-p2,
B = b.dist2()-p2, C = c.dist2()-p2;
return p.cross(a,b)*C + p.cross(b,c)*A + p.cross(c,a)*B > 0;
}
Q makeEdge(P orig, P dest) {
Q q[] = {new Quad{0,0,0,orig}, new Quad{0,0,0,arb},
new Quad{0,0,0,dest}, new Quad{0,0,0,arb}};
rep(i,0,4)
q[i]->o = q[-i & 3], q[i]->rot = q[(i+1) & 3];
return *q;
}
void splice(Q a, Q b) {
swap(a->o->rot->o, b->o->rot->o); swap(a->o, b->o);
}
Q connect(Q a, Q b) {
Q q = makeEdge(a->F(), b->p);
splice(q, a->next());
splice(q->r(), b);
return q;
}
pair<Q,Q> rec(const vector<P>& s) {
if (sz(s) <= 3) {
Q a = makeEdge(s[0], s[1]), b = makeEdge(s[1], s.back());
if (sz(s) == 2) return { a, a->r() };
splice(a->r(), b);
auto side = s[0].cross(s[1], s[2]);
Q c = side ? connect(b, a) : 0;
return {side < 0 ? c->r() : a, side < 0 ? c : b->r() };
}
#define H(e) e->F(), e->p
#define valid(e) (e->F().cross(H(base)) > 0)
Q A, B, ra, rb;
int half = sz(s) / 2;
tie(ra, A) = rec({all(s) - half});
tie(B, rb) = rec({sz(s) - half + all(s)});
while ((B->p.cross(H(A)) < 0 && (A = A->next())) ||
(A->p.cross(H(B)) > 0 && (B = B->r()->o)));
Q base = connect(B->r(), A);
if (A->p == ra->p) ra = base->r();
if (B->p == rb->p) rb = base;
#define DEL(e, init, dir) Q e = init->dir; if (valid(e)) \
while (circ(e->dir->F(), H(base), e->F())) { \
Q t = e->dir; \
splice(e, e->prev()); \
splice(e->r(), e->r()->prev()); \
e = t; \
}
for (;;) {
DEL(LC, base->r(), o); DEL(RC, base, prev());
if (!valid(LC) && !valid(RC)) break;
if (!valid(LC) || (valid(RC) && circ(H(RC), H(LC))))
base = connect(RC, base->r());
else
base = connect(base->r(), LC->r());
}
return { ra, rb };
}
vector<P> triangulate(vector<P> pts) {
sort(all(pts)); assert(unique(all(pts)) == pts.end());
if (sz(pts) < 2) return {};
Q e = rec(pts).first;
vector<Q> q = {e};
int qi = 0;
while (e->o->F().cross(e->F(), e->p) < 0) e = e->o;
#define ADD { Q c = e; do { c->mark = 1; pts.push_back(c->p); \
q.push_back(c->r()); c = c->next(); } while (c != e); }
ADD; pts.clear();
while (qi < sz(q)) if (!(e = q[qi++])->mark) ADD;
return pts;
}
// circumcenter
double ccRadius(const P& A, const P& B, const P& C) {
return (B-A).dist()*(C-B).dist()*(A-C).dist()/
abs((B-A).cross(C-A))/2;
}
P ccCenter(const P& A, const P& B, const P& C) {
P b = C-A, c = B-A;
return A + (b*c.dist2()-c*b.dist2()).perp()/b.cross(c)/2;
}
// point projection
template<class P>
P lineProj(P a, P b, P p, bool refl=false) {
P v = b - a;
return p - v.perp()*(1+refl)*v.cross(p-a)/v.dist2();
}
// polygon intersection
const double epsilon = 1e-9;
double segDist(P& s, P& e, P& p) {
if (s==e) return (p-s).dist();
auto d = (e-s).dist2(), t = min(d,max(.0,(p-s).dot(e-s)));
return ((p-s)*d-(e-s)*t).dist()/d;
}
template<class P> bool onSegment(P s, P e, P p) {
return segDist(s,e,p) <= epsilon;
}
template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
auto d = (e1 - s1).cross(e2 - s2);
if (d == 0) // if parallel
return {-(s1.cross(e1, s2) == 0), P(0, 0)};
auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
return {1, (s1 * p + e1 * q) / d};
}
// is point inside polygon
template<class P>
bool inPolygon(vector<P> &p, P a, bool strict = true) {
int cnt = 0, n = sz(p);
rep(i,0,n) {
P q = p[(i + 1) % n];
if (onSegment(p[i], q, a)) return !strict;
//or: if (segDist(p[i], q, a) <= eps) return !strict;
cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0;
}
return cnt;
}
// candidate point test
double testPoint(vector<P> &poly, P p) {
double ans = 1e18; int n = poly.size();
for (int i = 0; i < n; i++) {
ans = min(ans, (p - poly[i]).dist());
}
return ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<P> pol(n);
for (int i = 0; i < n; i++) {
cin >> pol[i].x >> pol[i].y;
}
// compute voronoi diagram
vector<P> delaunay = triangulate(pol);
vector<P> voronoi;
for (int i = 0; i < delaunay.size(); i += 3) {
voronoi.push_back(ccCenter(delaunay[i], delaunay[i+1], delaunay[i+2]));
}
// solving
double ans = 0;
// voronoi vertices
for (P p: voronoi) {
if (inPolygon(pol, p, false))
ans = max(ans, testPoint(pol, p));
}
// voronoi edges
for (int i = 0; i < delaunay.size(); i += 3) {
for (int j = 0; j < 3; j++) {
P P1 = voronoi[i/3];
P P2 = lineProj(delaunay[i+j], delaunay[i+((j+1) % 3)], P1, true);
for (int k = 0; k < n; k++) {
P cand = lineInter(P1, P2, pol[k], pol[(k+1) % n]).second;
if (onSegment(pol[k], pol[(k+1) % n], cand)) {
ans = max(ans, testPoint(pol, cand));
}
}
}
}
// output
cout << fixed << setprecision(12) << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 4016kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3800kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 4020kb
Test #14:
score: 0
Accepted
time: 0ms
memory: 3884kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 4012kb
Test #17:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #18:
score: 0
Accepted
time: 0ms
memory: 3848kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #20:
score: 0
Accepted
time: 0ms
memory: 3848kb
Test #21:
score: 0
Accepted
time: 0ms
memory: 3800kb
Test #22:
score: 0
Accepted
time: 0ms
memory: 3732kb
Test #23:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #24:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #25:
score: 0
Accepted
time: 0ms
memory: 3884kb
Test #26:
score: 0
Accepted
time: 0ms
memory: 3896kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3912kb
Test #28:
score: 0
Accepted
time: 0ms
memory: 3856kb
Test #29:
score: 0
Accepted
time: 0ms
memory: 3856kb
Test #30:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #31:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #32:
score: 0
Accepted
time: 0ms
memory: 4016kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 3960kb
Test #35:
score: 0
Accepted
time: 0ms
memory: 3888kb
Test #36:
score: 0
Accepted
time: 0ms
memory: 3744kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 4036kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #39:
score: 0
Accepted
time: 0ms
memory: 3888kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 4044kb
Test #42:
score: 0
Accepted
time: 0ms
memory: 3880kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #44:
score: 0
Accepted
time: 0ms
memory: 3736kb
Test #45:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #46:
score: 0
Accepted
time: 0ms
memory: 4016kb
Test #47:
score: 0
Accepted
time: 0ms
memory: 3880kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #49:
score: 0
Accepted
time: 0ms
memory: 3952kb
Test #50:
score: 0
Accepted
time: 0ms
memory: 3720kb
Test #51:
score: 0
Accepted
time: 0ms
memory: 3808kb
Test #52:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #53:
score: 0
Accepted
time: 13ms
memory: 4332kb
Test #54:
score: 0
Accepted
time: 61ms
memory: 4664kb
Test #55:
score: 0
Accepted
time: 2ms
memory: 3900kb
Test #56:
score: 0
Accepted
time: 59ms
memory: 4596kb
Test #57:
score: 0
Accepted
time: 393ms
memory: 5136kb
Test #58:
score: 0
Accepted
time: 3ms
memory: 4000kb
Test #59:
score: 0
Accepted
time: 170ms
memory: 4496kb
Test #60:
score: 0
Accepted
time: 1249ms
memory: 5168kb
Test #61:
score: 0
Accepted
time: 2ms
memory: 3852kb
Test #62:
score: 0
Accepted
time: 157ms
memory: 4104kb
Test #63:
score: 0
Accepted
time: 1162ms
memory: 4476kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #65:
score: 0
Accepted
time: 0ms
memory: 3796kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3804kb
Test #67:
score: 0
Accepted
time: 0ms
memory: 4024kb
Test #68:
score: 0
Accepted
time: 189ms
memory: 5180kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #70:
score: 0
Accepted
time: 192ms
memory: 5180kb
Test #71:
score: 0
Accepted
time: 10ms
memory: 4160kb
Test #72:
score: 0
Accepted
time: 162ms
memory: 5228kb
Test #73:
score: 0
Accepted
time: 31ms
memory: 4616kb
Test #74:
score: 0
Accepted
time: 194ms
memory: 4984kb
Test #75:
score: 0
Accepted
time: 50ms
memory: 4416kb
Test #76:
score: 0
Accepted
time: 5ms
memory: 4144kb
Test #77:
score: 0
Accepted
time: 5ms
memory: 4216kb
Test #78:
score: 0
Accepted
time: 5ms
memory: 4224kb
Test #79:
score: 0
Accepted
time: 5ms
memory: 4220kb
Test #80:
score: 0
Accepted
time: 6ms
memory: 4104kb
Test #81:
score: 0
Accepted
time: 6ms
memory: 4216kb
Test #82:
score: 0
Accepted
time: 6ms
memory: 3920kb
Test #83:
score: 0
Accepted
time: 6ms
memory: 4108kb
Test #84:
score: 0
Accepted
time: 5ms
memory: 4040kb
Test #85:
score: 0
Accepted
time: 5ms
memory: 4052kb
Test #86:
score: 0
Accepted
time: 5ms
memory: 4148kb
Test #87:
score: 0
Accepted
time: 5ms
memory: 3916kb
Test #88:
score: 0
Accepted
time: 5ms
memory: 3980kb
Test #89:
score: 0
Accepted
time: 5ms
memory: 4112kb
Test #90:
score: 0
Accepted
time: 5ms
memory: 3972kb
Test #91:
score: 0
Accepted
time: 5ms
memory: 3980kb
Test #92:
score: 0
Accepted
time: 766ms
memory: 5468kb
Test #93:
score: 0
Accepted
time: 743ms
memory: 5572kb
Test #94:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #95:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #96:
score: 0
Accepted
time: 4ms
memory: 3908kb
Test #97:
score: 0
Accepted
time: 2ms
memory: 4036kb
Test #98:
score: 0
Accepted
time: 1196ms
memory: 6624kb
Test #99:
score: 0
Accepted
time: 2880ms
memory: 6624kb
Test #100:
score: 0
Accepted
time: 1279ms
memory: 6580kb
Test #101:
score: 0
Accepted
time: 1280ms
memory: 6740kb
Test #102:
score: 0
Accepted
time: 1139ms
memory: 6516kb
Test #103:
score: 0
Accepted
time: 560ms
memory: 6240kb
Test #104:
score: 0
Accepted
time: 970ms
memory: 6484kb