Submission #667820

#TimeUsernameProblemLanguageResultExecution timeMemory
667820GusterGoose272circles (balkan11_2circles)C++11
100 / 100
412 ms12112 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef pair<ld, ld> pii; ld inf = 1e9; ld eps = 1e-8; const int MAXN = 5e4; pii operator+(pii a, pii b) { return pii(a.first+b.first, a.second+b.second); } ld cross(pii a, pii b) { return a.first*b.second-a.second*b.first; } ld dot(pii a, pii b) { return a.first*b.first+a.second*b.second; } pii operator-(pii a, pii b) { return pii(a.first-b.first, a.second-b.second); } pii operator*(pii a, ld b) { return pii(a.first*b, a.second*b); } pii operator/(pii a, ld b) { return a*(1/b); } pii operator*(ld b, pii a) { return a*b; } pii operator-(pii a) { return (-1)*a; } ld mag(pii a) { return sqrt(dot(a, a)); } class Line { public: pii start; pii vec; // ld rbound = inf; ld lbound = -inf; Line() {} Line(pii a, pii b) { start = a; vec = (b-a)/mag(b-a); } Line(Line other, ld x) { vec = other.vec; start = other.start+x*pii(-vec.second, vec.first); } pii get_point() { // assert(rbound < inf-eps); return start+vec*lbound; } }; ld cross(Line a, Line b) { return cross(a.vec, b.vec); } pii points[MAXN]; Line lines[MAXN]; Line lines_orig[MAXN]; pii points_temp[MAXN]; int n; ld mx_dist(int f, int t) { int s = f; ld best = 0; for (int i = f; i < t; i++) { while (s < t-1 && mag(points_temp[i]-points_temp[s]) < mag(points_temp[i]-points_temp[s+1])) s++; best = max(best, mag(points_temp[i]-points_temp[s])); } return best; } ld inter(Line a, Line b) { // distance in direction of vec from start of a return cross(b.start-a.start, b.vec)/cross(a.vec, b.vec); } bool possible(ld cur) { vector<int> hull; hull.push_back(0); for (int i = 1; i < n; i++) { if (cross(lines[hull.back()], lines[i]) < eps) return 0; while (hull.size() > 1 && cross(lines[i].vec, lines[hull.back()].get_point()-lines[i].start) < eps) { hull.pop_back(); if (cross(lines[hull.back()], lines[i]) < eps) return 0; } lines[i].lbound = inter(lines[i], lines[hull.back()]); hull.push_back(i); } // now check collisions between front & back int s = 0; bool b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps; bool b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps; while (hull.size() > 3 && (b1 || b2)) { if (b1) { hull.pop_back(); } if (b2) { s++; } b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps; b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps; } lines[hull[s]].lbound = inter(lines[hull[s]], lines[hull.back()]); for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point(); return (mx_dist(s, hull.size()) > 2*cur); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 0; i < n; i++) cin >> points[i].first >> points[i].second; for (int i = 0; i < n; i++) { lines_orig[i] = Line(points[i], points[(i+1)%n]); } ld mn = 0; ld mx = 6e6; for (int i = 0; i < 100; i++) { ld cur = (mn+mx)/2; for (int i = 0; i < n; i++) lines[i] = Line(lines_orig[i], cur); if (possible(cur)) mn = cur; else mx = cur; } cout << fixed << setprecision(3) << mn << "\n"; }

Compilation message (stderr)

twocircles.cpp: In function 'bool possible(ld)':
twocircles.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point();
      |                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...