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
#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 d)
{
return pt(a.x * d, a.y * d);
}
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);
}
pt project_to_segment(pt a, pt b, pt c)
{
double r = sqrLen(b - a);
if (abs(r) < eps)
return a;
r = dot(c - a, b - a) / r;
if (r < 0)
return a;
if (r > 1)
return b;
return a + (b - a) * r;
}
double dist_to_segment(pt c, pt a, pt b)
{
return len(c - project_to_segment(a, b, c));
}
double find_r_pos(pt a, vector<pt>& ver)
{
double r_ans = 1e9;
for (int i = 0; i < ver.size(); i++)
r_ans = min(r_ans, dist_to_segment(a, ver[i], ver[(i+1)%ver.size()]));
return r_ans;
}
double coord[3];
void tern_search(vector<pt>& ver, double& ans, int i)
{
if (i == 2){
pt check = pt(coord[0], coord[2]);
ans = max(ans, find_r_pos(check, ver));
return;
}
double border_left = -1e7;
double border_right = 1e7;
while (border_right - border_left > eps){
double left_coord = border_left + (border_right - border_left) / 3;
double right_coord = border_right - (border_right - border_left) / 3;
coord[i] = left_coord;
tern_search(ver, ans, i + 1);
coord[i] = right_coord;
tern_search(ver, ans, i + 1);
}
}
double solve(int n)
{
double ans = -1;
vector<pt> ver(n);
double most_left_x = 1e9;
double most_right_x = -1e9;
double most_up_y = -1e9;
double most_down_y = 1e9;
for (int i = 0; i < n; i++){
cin >> ver[i].x >> ver[i].y;
most_right_x = max(most_right_x, ver[i].x);
most_left_x = min(most_left_x, ver[i].x);
most_up_y = max(most_up_y, ver[i].y);
most_down_y = min(most_down_y, ver[i].y);
}
tern_search(most_left_x, most_right_x, ver, ans);
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin >> n;
cout << fixed << setprecision(3) << solve(n) << endl;
return 0;
}