#include #include #include #include using namespace std; const double eps = 1e-8; struct pt { double x; double y; pt(double X = 0, double Y = 0): x(X), y(Y){}; }; pt operator+(pt a, pt b) { return pt(a.x + b.x, a.y + b.y); } pt operator-(pt a, pt b) { return pt(a.x - b.x, a.y - b.y); } pt operator*(pt a, double v) { return pt(a.x * v, a.y * v); } double sqrLen(pt a) { return a.x * a.x + a.y * a.y; } double len(pt a) { return sqrt(sqrLen(a)); } double dot(pt a, pt b) { return a.x * b.x + a.y * b.y; } double cross(pt a, pt b) { return a.x * b.y - a.y * b.x; } bool check_intersect(pt c1, pt c2, double r1, double r2) { pt v1 = c1 - c2; return (sqrLen(v1) > (r1 + r2) * (r1 + r2) || sqrLen(v1) < eps); } pt normalize(pt a) { double length = len(a); return pt(a.x / length, a.y / length); } pair rotate(pt a, double cos_alfa, double sin_alfa) { pair ans; ans.first = pt (a.x * cos_alfa + a.y * sin_alfa, -sin_alfa * a.x + cos_alfa * a.y); ans.second = pt (a.x * cos_alfa - a.y * sin_alfa, sin_alfa * a.x + cos_alfa * a.y); return ans; } pair intersect_circles(pt c1, pt c2, double r1, double r2) { pair ans; pt v1 = c2 - c1; double cos_alfa = (sqrLen(v1) + r1 * r1 - r2 * r2) / (2 * len(v1) * r1); double sin_alfa = sqrt(1 - cos_alfa * cos_alfa); pt v_norm_r = normalize(v1) * r1; pair rot_rez = rotate(v_norm_r, cos_alfa, sin_alfa); ans.first = c1 + rot_rez.first; ans.second = c1 + rot_rez.second; return ans; } bool is_blank(vector& plants, int ind1, int ind2, pt c, double r_pos) { for (int i = 0; i < plants.size(); i++) if (i != ind1 && i != ind2) if (sqrLen(c-plants[i]) < r_pos * r_pos + eps) return false; return true; } bool check_blanks(vector& plants, double r_pos, double r_city) { for (int i = 0; i < plants.size(); ++i) if (r_pos > r_city && (r_city - r_pos) * (r_city - r_pos)>= sqrLen(plants[i])) return false; if (plants.size() == 1) return true; pt centre = pt(0, 0); bool no_points = true; for (int i = 0; i < plants.size(); i++){ pair temp; if (check_intersect(centre, plants[i], r_city, r_pos)){ temp = intersect_circles(centre, plants[i], r_city, r_pos); if (is_blank(plants, i, i, temp.first, r_pos) || is_blank(plants, i, i, temp.second, r_pos)) return true; } for (int j = i + 1; j < plants.size(); j++){ if (check_intersect(plants[i], plants[j], r_pos,r_pos)){ no_points = false; temp = intersect_circles(plants[i], plants[j], r_pos, r_pos); if(sqrLen(temp.first) < r_city * r_city + eps && is_blank(plants, i, j, temp.first, r_pos)|| sqrLen(temp.second) < r_city * r_city + eps && is_blank(plants, i, j, temp.second, r_pos)) return true; } } } return no_points; } void bin_search(double& r_left, double& r_right, double r_city, vector& plants) { double r_mid = (r_left + r_right) / 2; if (check_blanks(plants, r_mid, r_city)){ r_left = r_mid; bin_search(r_left, r_right, r_city, plants); } else{ r_right = r_mid; bin_search(r_left, r_right, r_city, plants); } } double solve(int n, double r_city) { double ans_r = 1e4; vector plants(n); for (int i = 0; i < n; i++) cin >> plants[i].x >> plants[i].y; double r_left = 0; double r_right = 2 * 1e3 + 1; bin_search(r_left, r_right, r_city, plants); ans_r = (r_left + r_right) / 2; return ans_r; } int main() { ios_base::sync_with_stdio(false); int n, r; cout << setprecision(6) << fixed << solve(n, r) << endl; return 0; }