#include using namespace std; typedef long long int ll; typedef double ld; typedef vector vi; // push_back insert lower_bound upper_bound erase #define F(a) for ( ll i = 0; i < (ll)(a); ++i ) // 1e-12 is too low #define EPS (1e-10) //bool eq(ld a, ld b) { return fabs(a-b) <= fabs(a+b) * EPS; } // cannot compare very small numbers to each other bool eq(ld a, ld b) { return abs(a-b) <= EPS; } int dcmp(ld x){ return (fabs(x)>(istream &is, Pt &a){ is>>a.x>>a.y; return is; } }; struct Line { Pt a, b; ll side; // 0=east-west, 1=north-south, 2=outside the roof bool operator<(Line &l){ Pt v=b-a, w=l.b-l.a; return atan2(v.y, v.x) < atan2(w.y, w.x); } }; ld vec(Pt a, Pt b){ return a.x*b.y-a.y*b.x; } ld vec(Pt a, Pt b, Pt c){ return vec(b-a, c-a); } ld dot(Pt a, Pt b){ return a.x*b.x+a.y*b.y; } ld norm(Pt a){ return hypot(a.x, a.y); } ld line_point_dist(Line l, Pt p){ return fabs(vec(p-l.a, l.b-l.a)/norm(l.b-l.a)); } Pt scale_to(Pt a, ld res){ return a*res/norm(a); } Pt normal(Pt a){ ld n=norm(a); return {-a.y/n, a.x/n}; } ld angle2(Pt a, Pt b){ a=scale_to(a, 1); b=scale_to(b, 1); ld ang=acos(dot(a, b)); //ld ang=acos(dot(a, b)/norm(a)/norm(b)); if(ang>M_PI)ang-=2*M_PI; return ang; } ld angle(Pt a, Pt b){ ld ang=atan2(vec(a,b),dot(a,b)); if(ang>M_PI)ang-=2*M_PI; if(ang<-M_PI)ang+=2*M_PI; return ang; } Pt lines_intersection(Line p, Line q){ Pt v=p.b-p.a; Pt w=q.b-q.a; ld t=vec(w, p.a-q.a)/vec(v, w); return p.a+v*t; } Pt line_point_closest_point(Line a, Pt b){ return lines_intersection(a, {b, b+normal(a.b-a.a)}); } bool is_point_on_segment(Pt p, Line s){ return dcmp(vec(s.a-p, s.b-p))==0 && dcmp(dot(s.a-p, s.b-p))<=0; } bool is_point_in_polygon_clock(Pt p, vector &lines){ for(Line &l:lines)if(is_point_on_segment(p, l))return true; ld sum = 0; for(Line &l:lines){ ld ang=angle(l.a-p, l.b-p); //cerr<<"angle: "< &lines){ ll n=lines.size(), wn=0; for(int i=0; i0 && d1<=0 && d2>0) wn++; if(k<0 && d2<=0 && d1>0) wn--; } return wn;// wn=1 point is inside, 0 outisde } bool point_is_inside2(Pt p, vector &poly){ for(Line &l:poly)if(is_point_on_segment(p, l))return true; ll r=0; p.x += EPS/2; p.y += EPS/2; for(int i=0; i<4; ++i){ ll cnt = 0; for(Line &l:poly){ if(p.y < l.a.y) if(l.a.x < p.x+EPS && p.x < l.b.x || l.b.x < p.x+EPS && p.x < l.a.x) cnt+=1; } if((cnt%2) == 0) r++; swap(p.x,p.y); p.y=-p.y; } return r<4; } bool point_is_inside(Pt p, vector &poly){ vector res; //res.push_back(point_is_inside2(p, poly)); //res.push_back(is_point_in_polygon(p, poly)); res.push_back(is_point_in_polygon_clock(p, poly)); assert(res.size()); //cerr<<"inside?: "; F(res.size())cerr< a; vector lines; void load(){ cin>>N; cin>>l.a>>l.b; Pt d=l.b-l.a; a.assign(N, {}); F(N) cin>>a[i]; lines.assign(N, {}); F(N) lines[i]={a[i], a[(i+1)%N]}; F(N) lines[i].side=lines[i].a.y==lines[i].b.y; } Pt point_from_ratio(ld ratio){ return l.a*(1-ratio)+l.b*ratio; } pair find_closest_side(ld ratio){ Pt center = point_from_ratio(ratio); ld dist=1e60; ll id=-1; bool inside = point_is_inside(center, lines); F(N){ Pt d1=center-lines[i].a; Pt d2=center-lines[i].b; ld d=dist; if(!inside || vec(lines[i].a, lines[i].b, center)>=-EPS){ if(d1.x==d2.x && (d1.y*d2.y<0 || min(abs(d1.y),abs(d2.y)) <= abs(d1.x))) { d=min(d, abs(d1.x)); } if(d1.y==d2.y && (d1.x*d2.x<0 || min(abs(d1.x),abs(d2.x)) <= abs(d1.y))) { d=min(d, abs(d1.y)); } } //cerr<<"point "< bsearch(ld low, ld high, ll low_edge_id){ ld mid; //cerr< max_step){ // the biggest allowed step mid = low+max_step/line_length; } //cerr< "<=0); if(last<0){ cerr<<"LAST: "<=0); vector path; path.push_back({0.0, first}); ll current_eid=first; ld current_ratio=0.0; //cout<<"0\n";return 0; while(current_ratio < 1.-EPS){ //cerr< p=bsearch(current_ratio, 1.0, current_eid); ld new_ratio = p.first; //cerr<<"find_closest_side\n"; ll new_eid = p.second; path.push_back({new_ratio, new_eid}); //cerr<<"current ratio: "<= 0 && side <= 2); side_sum[side]+=dif; } ld sum=side_sum[0]*(hypot(1, abs(cos(line_ang))))+side_sum[1]*(hypot(1, abs(sin(line_ang))))+side_sum[2]; ld res=sum*hypot(ldif.x, ldif.y); cout<