include iostream include vector include cmath include iomanip using na

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
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<pt, pt> rotate(pt a, double cos_alfa, double sin_alfa)
{
pair<pt, pt> 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<pt, pt> intersect_circles(pt c1, pt c2, double r1, double r2)
{
pair<pt, pt> 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<pt, pt> 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<pt>& 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<pt>& 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<pt, pt> 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<pt>& 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<pt> 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;
}