#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); } friend ostream &operator<<(ostream &os, const Line &l){ os<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 "<=0 ? lines[eid].side : 2; side_sum[side]+=step; }else{ ll side = eid>=0 ? lines[eid].side : 2; ll lide = lastid>=0 ? lines[lastid].side : 2; side_sum[side]+=step/2; side_sum[lide]+=step/2; //cerr<<"at "< "<