#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 old_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 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); Pt res=p.a+v*t; //assert(fabs((ld)0 - vec(p.a,p.b,res))<1e-2); //assert(fabs((ld)0 - vec(q.a,q.b,res))<1e-2); return res; } 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=eq(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){ if(!(ratio>-2*EPS && ratio<1+2*EPS)){ cerr<<"ratio: "<=-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; // build all interesting points vector crosses; // which cross with outer lines for(Line a:lines){ if(segment_intersect(l, a)){ Pt cross_point = lines_intersection(l, a); crosses.push_back(cross_point); } } // or lie at possible roof angle for(int i=0; i0 ? -1. : 1.; Pt origin = lines_intersection(q, w); //cerr<<"o: "< interesting_ratios; interesting_ratios.push_back(0.); interesting_ratios.push_back(1.); ld prev_ratio=-1; for(Pt cross:crosses){ ld dist=points_distance(l.a, cross); //cerr<EPS/2) && ratio>=-EPS && ratio < 1+EPS){ interesting_ratios.push_back(ratio); prev_ratio=ratio; } } sort(interesting_ratios.begin(), interesting_ratios.end()); for(ld new_ratio : interesting_ratios){ ll new_eid = find_closest_side(new_ratio).first; path.push_back({new_ratio, new_eid}); } path.push_back({1.0, last}); ld side_sum[3]; side_sum[0]=side_sum[1]=side_sum[2]=0; // north-south, east-west, outside ll last_side=-2; F(path.size()-1){ ld dif=path[i+1].ratio-path[i].ratio; if(dif>EPS){ ld eid=path[i].eid; ld ratio=path[i].ratio; //Pt center=l.a*(1-ratio)+l.b*ratio; ll side=path[i].state; assert(side >= 0 && side <= 2); side_sum[side]+=dif; //if(last_side != side){ //cerr<