제출 #957497

#제출 시각아이디문제언어결과실행 시간메모리
957497kobor두 개의 원 (balkan11_2circles)C++17
100 / 100
598 ms6540 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...