Submission #223865

#	Time	Username	Problem	Language	Result	Execution time	Memory
223865		Bruteforceman	2circles (balkan11_2circles)	C++11	60 / 100	1510 ms	5772 KiB

twocircles

#include <bits/stdc++.h>
using namespace std;
typedef double T;

struct pt {

  T x,y;

  pt(T x=0, T y=0): x(x), y(y) {}

  pt operator+(pt p) { return {x+p.x, y+p.y}; }

  pt operator-(pt p) { return {x-p.x, y-p.y}; }

  pt operator*(T d) { return {x*d, y*d}; }

  pt operator/(T d) { return {x/d, y/d}; } 

};

bool operator==(pt a,pt b){return a.x==b.x&&a.y==b.y;}

bool operator!=(pt a, pt b) { return !(a == b); }

ostream& operator<<(ostream& os, pt p) {

  return os << "("<< p.x << "," << p.y << ")";

}

T sq(pt p) { return p.x*p.x + p.y*p.y; }

double abs(pt p) { return sqrt(sq(p)); }

T dot(pt v, pt w) { return v.x*w.x + v.y*w.y; }

T cross(pt v, pt w) { return v.x*w.y - v.y*w.x; }

template <typename T> int sgn(T x) {

  return (T(0) < x) - (x < T(0));

}
const double eps = 1e-9;



struct line {

  pt v; T c;

  // from direction vector v and offset c

  line(pt v, T c) : v(v), c(c) {}

  // from equation ax+by=c

  line(T a, T b, T c) : v({b,-a}), c(c) {}

  // from points P and Q

  line(pt p, pt q) : v(q-p), c(cross(v,p)) {}

  T side(pt p) { return cross(v,p)-c; }

};

// intersection of two lines

bool inter(line l1, line l2, pt &out) {

  T d = cross(l1.v, l2.v);

  if(d == 0) return false;

  out = (l2.v*l1.c - l1.v*l2.c) / d; 

  return true;

}

struct hp_t {

  pt p1, p2;

  double a;

  hp_t() { }

  hp_t(pt tp1, pt tp2) : p1(tp1), p2(tp2) {

    tp2 = tp2 - tp1;

    a = atan2(tp2.y, tp2.x);

  }

  bool operator==(const hp_t &r) const {

    return fabs(a - r.a) < eps; 

  }

  bool operator<(hp_t &r) {

    if(fabs(a - r.a) < eps) 

        return cross(r.p2 - r.p1, p2 - r.p1) >= -eps;

    else return a < r.a;

  }

} hp[50010];



int cnt;

void addhp(pt p1, pt p2) { 
  // cout << p1.x << " " << p1.y << " to " << p2.x << " " << p2.y << endl;
  hp[++cnt] = hp_t(p1, p2); 
}



double maxd = 1e8;

void init() {

  cnt = 0;

  addhp(pt(-maxd, -maxd), pt(maxd, -maxd));

  addhp(pt(maxd, -maxd), pt(maxd, maxd));

  addhp(pt(maxd, maxd), pt(-maxd, maxd));

  addhp(pt(-maxd, maxd), pt(-maxd, -maxd));

}

bool checkhp(hp_t h1, hp_t h2, hp_t h3) {

  pt p; 

  inter(line(h1.p1, h1.p2), line(h2.p1, h2.p2), p);

  return cross(p - h3.p1, h3.p2 - h3.p1) > eps;

}

vector<pt> ishp() {

  sort(hp + 1, hp + 1 + cnt);

  cnt = unique(hp + 1, hp + 1 + cnt) - hp - 1;

  deque<hp_t> dq;

  dq.push_back(hp[1]);

  dq.push_back(hp[2]);

  for (int i = 3; i <= cnt; ++i) {

    while (dq.size() > 1 && checkhp(*----dq.end(), 

              *--dq.end(), hp[i])) dq.pop_back();

    while (dq.size() > 1 && checkhp(*++dq.begin(), 

              *dq.begin(), hp[i])) dq.pop_front();

    dq.push_back(hp[i]);

  }

  while (dq.size() > 1 && checkhp(*----dq.end(), 

            *--dq.end(), dq.front())) dq.pop_back();

  while (dq.size() > 1 && checkhp(*++dq.begin(), 

            *dq.begin(), dq.back())) dq.pop_front();

  dq.push_front(dq.back());

  vector<pt> res;

  while (dq.size() > 1) {

    hp_t tmp = dq.front();

    dq.pop_front();

    pt I; 

    inter(line(tmp.p1, tmp.p2), 

          line(dq.front().p1, dq.front().p2), I);

    res.push_back(I);

  }

  return res;

}

int n;
pt v[50010];
pt orthogonal(pt a, double len) {
  double x = -a.y;
  double y = a.x;
  double mag = sqrt(x*x + y*y);
  return pt(x * (len / mag), y * (len / mag));
}

double diameter(vector <pt> v) {
  auto dist = [&] (pt a, pt b) {
    return dot(a - b, a - b);
  };
  double ans = 0;
  int k = v.size();
  for(int i = 0; i < k; i++) {
    int l = 0, r = k - 1;
    while(l < r) {
      int m = (l + r) >> 1;
      if(dist(v[i], v[(i + m) % k]) <= dist(v[i], v[(i + m + 1) % k])) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    ans = max(ans, dist(v[i], v[l]));
  }
  return sqrt(ans) / 2;
}

bool good(double g) {
  cnt = 0;
  init();
  for(int i = 0; i < n; i++) {
    pt shift = orthogonal(v[(i + 1) % n] - v[i], g);
    addhp(v[i] + shift, v[(i + 1) % n] + shift);
//     cout << shift.x << ' ' << shift.y << endl;
  }
  vector <pt> p = ishp();
  return diameter(p) >= g; 
}  

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> v[i].x >> v[i].y;
  }
  double l = 0, r = 3e7;
  for(int i = 0; i < 100; i++) {
    double m = (l + r) * 0.5;
    if(good(m)) l = m;
    else r = m;
  }
  cout << setprecision(3) << fixed << l << endl;
  return 0;
}

• Subtask 1: 60 / 100