Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <map>
- #define eps 1e-8
- #define INF 1000000
- #define PI 3.14159265359
- using namespace std;
- struct point
- {
- double x, y;
- point(double x = 0, double y = 0) :x(x), y(y) {}
- };
- bool operator == (const point& a, const point& b)
- {
- return fabs(a.x - b.x) < eps && fabs(a.y - b.y) < eps;
- }
- bool operator != (const point& a, const point& b)
- {
- return !(a == b);
- }
- bool operator < (const point& a, const point& b)
- {
- return (a.x + eps < b.x) || (fabs(a.x - b.x) < eps && (a.y + eps < b.y));
- }
- point operator-(point a, point b)
- {
- return point(a.x - b.x, a.y - b.y);
- }
- point operator+(point a, point b)
- {
- return point(a.x + b.x, a.y + b.y);
- }
- point operator*(point a, double k)
- {
- return point(a.x*k, a.y*k);
- }
- point operator/(point a, double k)
- {
- return point(a.x / k, a.y / k);
- }
- double dist2(point a, point b = point(0, 0))
- {
- point c = (a - b);
- return (c.x*c.x) + (c.y*c.y);
- }
- double dist(point a, point b = point(0, 0))
- {
- return sqrt(dist2(a, b));
- }
- point perp(point a)
- {
- return point(a.y, -a.x);
- }
- point norm(point p)
- {
- return p / dist(p);
- }
- double dot(point a, point b)
- {
- return a.x*b.x + a.y*b.y;
- }
- struct Edge
- {
- point a, b;
- double w;
- Edge(point a, point b, double w) :a(a), b(b), w(w) {}
- };
- point intersect_circle_circle(point o, double r, point O, double R, bool up = true)
- {
- double d = dist(o, O)/2.0;
- double h = sqrt(R*R-d*d);
- point H = (o+O)/2.0;
- if (up)
- {
- point p = perp(norm(O - o))*h;
- point a = (O - o);
- a = norm(a);
- a = perp(a);
- a = a*h;
- return H + a;
- }
- else
- {
- point p = perp(norm(O - o))*h;
- point a = (O - o);
- a = norm(a);
- a = perp(a);
- a = a*h;
- return H - a;
- }
- }
- bool point_in_circle(point p, point O, double r)
- {
- return dist2(p, O)-eps <= r*r;
- }
- double r;
- vector<point> get_all_points(const vector<point>& v, double t)
- {
- vector<point> p;
- for (int i = 0; i < v.size(); i++)
- for (int j = i+1; j < v.size(); j++)
- if (v[i] != v[j])
- {
- p.push_back(intersect_circle_circle(v[i], t, v[j], t));
- p.push_back(intersect_circle_circle(v[i], t, v[j], t, false));
- }
- return p;
- }
- bool exist_intersect_circle_circle(point o, double r, point O, double R)
- {
- return (r + R >= dist2(o, O)) && (dist(o, O) + r >= R) && (dist(o, O) + R >= r);
- }
- int count_of_intersections(point O, const vector<point>& v, double t)
- {
- int k = 0;
- for (int i = 0; i < v.size(); i++)
- k += point_in_circle(O, v[i], t);
- return k;
- }
- bool check(const vector<point>& v, double t)
- {
- vector<point> p = get_all_points(v, t);
- for (int i = 0; i < p.size(); i++)
- {
- if (count_of_intersections(p[i], v, t) < 3 && point_in_circle(p[i], point(0, 0), r))
- return false;
- }
- return true;
- }
- int main()
- {
- int n;
- cin >> n >> r;
- vector<point> v(n);
- for (int i = 0; i < n; i++)
- {
- cin >> v[i].x >> v[i].y;
- }
- sort(v.begin(), v.end());
- v.erase(unique(v.begin(), v.end()), v.end());
- double left = 0, right = 4*r + 1.0;
- while (right - left > eps)
- {
- double t = (left + right) / 2;
- if (check(v, t))
- right = t;
- else
- left = t;
- }
- cout << fixed << setprecision(8) << left << endl;
- //cout << fixed << setprecision(3) << ans.x << " " << fixed << setprecision(3) << ans.y;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement