#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
using P = Point;
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 << ")"; }
};
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};
}
using P = Point<double>;
int hf(P a) { return a.y < 0 || (a.y == 0 && a.x < 0); }
struct polarCmp {
bool operator()(const P &a, const P &b) const {
return hf(a) == hf(b) ? a.cross(b) > 0 : hf(a) < hf(b);
}
};
struct HalfplaneSet : map<P, P, polarCmp> {
double INF = 1e8, area = 8 * INF * INF;
HalfplaneSet() {
P p(-INF, -INF), d(1, 0);
FOR(k, 0, 4) {
insert({d, p});
p = p + d * 2 * INF;
d = d.perp();
}
}
auto fix(auto it) { return it == end() ? begin() : it; }
auto getNext(auto it) { return fix(next(it)); }
auto getPrev(auto it) {
return it == begin() ? prev(end()) : prev(it);
}
auto uSide(auto it, int change) { // 1 - add, -1 - del
area += change * it->nd.cross(getNext(it)->nd);
}
auto del(auto it) {
uSide(getPrev(it), -1), uSide(it, -1);
it = fix(erase(it));
if(size()) uSide(getPrev(it), 1);
return it;
}
void add(P s, P e) {
deb(s, e);
auto eval = [&](auto it) {
return sgn(s.cross(e, it->nd));
};
auto intersect = [&](auto it) {
return lineInter(s, e, it->nd, it->st + it->nd).nd;
};
auto it = fix(lower_bound(e - s));
if(empty() || eval(it) >= 0) return;
while(size() && eval(getPrev(it)) < 0) del(getPrev(it));
while(size() && eval(getNext(it)) < 0) it = del(it);
if(empty()) return;
if(eval(getNext(it)) > 0) {
uSide(getPrev(it), -1), uSide(it, -1);
it->nd = intersect(it);
uSide(getPrev(it), 1), uSide(it, 1);
}
else it = del(it);
it = getPrev(it);
uSide(it, -1);
insert(it, {e - s, intersect(it)});
uSide(it, 1), uSide(getNext(it), 1);
if(eval(it) == 0) del(it);
}
double maxDot(P a) {
return a.dot(fix(lower_bound(a.perp()))->nd);
}
double getArea() { return area / 2; }
};
void solve() {
int n;
cin >> n;
vector<P> pts;
FOR(i, 0, n) {
int x, y;
cin >> x >> y;
pts.pb(P(x, y));
}
auto check = [&](double r) {
HalfplaneSet jan;
FOR(i, 0, n) {
P s = pts[i], e = pts[(i + 1) % n];
P d = (e - s).normal() * r;
jan.add(s + d, e + d);
}
vector<P> cnd;
for(auto &[_, pt]: jan) cnd.pb(pt);
if(SZ(cnd) == 0) return false;
double best = 0;
int j = 1 % SZ(cnd);
FOR(i, 0, SZ(cnd)) {
P a = cnd[i], b = cnd[(i + 1) % SZ(cnd)];
while(a.cross(b, cnd[j]) < a.cross(b, cnd[(j + 1) % SZ(cnd)])) j = (j + 1) % SZ(cnd);
for(P cand: {a, b}) best = max(best, (cand - cnd[j]).dist());
}
return best >= r * 2;
};
double l = 0, r = 1e8;
FOR(it, 0, 60) {
double mid = (l + r) / 2;
(check(mid) ? l : r) = mid;
}
cout << fixed << setprecision(9);
cout << l << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin >> tt;
FOR(te, 0, tt) solve();
return 0;
}
Compilation message
twocircles.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
twocircles.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
twocircles.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
twocircles.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
twocircles.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
twocircles.cpp:89:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
89 | auto fix(auto it) { return it == end() ? begin() : it; }
| ^~~~
twocircles.cpp:90:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
90 | auto getNext(auto it) { return fix(next(it)); }
| ^~~~
twocircles.cpp:91:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
91 | auto getPrev(auto it) {
| ^~~~
twocircles.cpp:95:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
95 | auto uSide(auto it, int change) { // 1 - add, -1 - del
| ^~~~
twocircles.cpp:99:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
99 | auto del(auto it) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
28 ms |
600 KB |
Output is correct |
| 6 |
Correct |
138 ms |
1944 KB |
Output is correct |
| 7 |
Correct |
158 ms |
988 KB |
Output is correct |
| 8 |
Correct |
244 ms |
2016 KB |
Output is correct |
| 9 |
Correct |
386 ms |
4060 KB |
Output is correct |
| 10 |
Correct |
598 ms |
6540 KB |
Output is correct |
