QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334144#2433. Panda Preserveneko_nyaaAC ✓2880ms6740kbC++236.7kb2024-02-21 11:09:302024-02-21 11:09:30

Judging History

你现在查看的是最新测评结果

  • [2024-02-21 11:09:30]
  • 评测
  • 测评结果:AC
  • 用时:2880ms
  • 内存:6740kb
  • [2024-02-21 11:09:30]
  • 提交

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;
}

Details

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