#include using namespace std; typedef long double ld; struct vec2{ ld x,y; vec2(ld x=0,ld y=0):x(x),y(y){} vec2 operator+(vec2 const &a)const{return {x+a.x,y+a.y};} vec2 operator-(vec2 const &a)const{return {x-a.x,y-a.y};} vec2 operator*(ld const a)const{return {x*a,y*a};} vec2 operator/(ld const a)const{return {x/a,y/a};} ld cross(vec2 const &a)const{return y*a.x-x*a.y;} ld dot(vec2 const &a)const{return x*a.x+y*a.y;} ld length()const{return hypotl(x,y);} vec2 normalize() {return (*this)/length();} }; optional project_onto_ray(vec2 const &p,vec2 const &a,vec2 const &b,bool clip=false){ ld const prj=(b-a).dot(p-a); ld const det=(b-a).dot(b-a); if (det==0){ return nullopt; } ld by=(prj/det); if (clip){ by=max(0.L,min(1.L,by)); } return make_optional(a+(b-a)*by); } vector circle_circle(vec2 const &a,vec2 const &b,ld const r){ vec2 c=(a+b)/2; ld edge2=r*r - (c-a).dot(c-a); if (edge2<0){ return {}; }else if (edge2==0){ return {c}; }else{ ld off=sqrtl(edge2); vec2 perp=vec2(b.y-a.y,a.x-b.x).normalize(); return {c+perp*off,c-perp*off}; } } vector circle_line(vec2 const &c,ld const r,vec2 const &a,vec2 const &b){ optional op=project_onto_ray(c,a,b,false); if (not op) return {}; vec2 const p=*op; ld const edge2=r*r - (p-c).dot(p-c); if (edge2<0){ return {}; }else if (edge2==0){ return {p}; }else{ ld const off=sqrtl(edge2); vec2 perp=(b-a).normalize(); vector result; vec2 u=(p+perp*off); vec2 v=(p-perp*off); if ((u-a).dot(b-a)>=0 and (b-u).dot(b-a)>=0) result.push_back(u); if ((v-a).dot(b-a)>=0 and (b-v).dot(b-a)>=0) result.push_back(v); return result; } } optional line_line(vec2 const &a,vec2 const &b,vec2 const &u,vec2 const &v){ if ((b-a).cross(v-u)==0) return nullopt; ld const s=(b-a).cross(a-u) / (b-a).cross(v-u); ld const t=(v-u).cross(u-a) / (v-u).cross(b-a); if (s<0 or s>1 or t<0 or t>1) return nullopt; return a+(b-a)*t; } ld polygon_area(vector const &p){ ld res=0.L; for (int i=0,j=p.size()-1; i const &p){ int crossings=0; for (int i=0,j=p.size()-1; i const &p){ ld closest=1e10L; for (int i=0,j=p.size()-1; i check(vector const &p,ld const r){ // Generate lines inset by ``r'' vector> l; for (int i=0,j=p.size()-1; i poi; // Circle-circle for (int i=p.size(); i--;) for (int j=i; j--;) for (vec2 const u: circle_circle(p[i],p[j],r)) poi.push_back(u); // Circle-line for (int i=p.size(); i--;) for (int j=l.size(); j--;) for (vec2 const u: circle_line(p[i],r,l[j].first,l[j].second)) poi.push_back(u); // Line-line for (int i=l.size(); i--;) for (int j=i; j--;) if (auto const u=line_line(l[i].first,l[i].second,l[j].first,l[j].second)) poi.push_back(*u); // Search for valid answers for (vec2 const &c: poi) if (point_in_polygon(c,p) and distance_to_polygon(c,p)>=r-1e-10L) return make_optional(c); return nullopt; } // O(N^3 x log(Precision)) int main(){ ld vel; cin>>vel; int n; cin>>n; vector poly(n); for (vec2 &i: poly) cin>>i.x>>i.y; if (polygon_area(poly)<0){ reverse(poly.begin(),poly.end()); } pair best={0.L,poly[0]}; for (long double span=powl(2,20); span>=1e-12L; span/=2.L){ ld candidate=best.first+span; auto const res=check(poly,candidate); if (res){ best={candidate,*res}; } } cout.precision(10); cout<