#include using namespace std; typedef int64_t ll; typedef long double ld; // O(N^2 * log(N)) // #define USE_FLOATS // #define DEBUG struct vec2{ ll x,y; vec2 operator-(vec2 const &a)const{ return {x-a.x,y-a.y}; } vec2 operator -()const{ return {-x,-y}; } ll operator *(vec2 const &a)const{ return y*a.x-x*a.y; } }; #ifdef USE_FLOATS typedef ld Fraction; ld evaluate(Fraction x){return x;} Fraction mf(ld a,ld b){return a/b;} #else struct Fraction{ ll n,d; Fraction(ll n, ll d=1):n(n),d(d){ simplify(); } Fraction(const Fraction &other): n(other.n), d(other.d){} void simplify(){ if (d<0) n=-n, d=-d; if (n==0) d=1; ll const g=__gcd(abs(n),d); n/=g, d/=g; } bool operator==(Fraction const &a)const{ if (n==0 or a.n==0) return n==0 and a.n==0; return n*a.d==a.n*d; } bool operator<(Fraction const &a)const{ return n*a.d(ll const &a)const{ return n>a*d; } ld evaluate() const{ return n/(ld)d; } }; ld evaluate(Fraction f) { return f.evaluate(); } Fraction mf(ll a,ll b){return Fraction(a,b);} #endif /* * If the line (a,a+fd) intersects the ray (b,b+bd), this returns a pair of: * * - intersect_point: the unique coordinate of the intersection * * - intersect_side: false if the line crosses the ray "left-to-right" (exiting a shape bounded * by it), false if crossing "right-to-left" (entering a shape bounded by it). * This assumes the ray is part of a CCW-specified polygon. * * If the line does not intersect the ray or line and ray are colinear, this returns nullopt. */ optional> line_ray(vec2 a,vec2 ad,vec2 b,vec2 bd){ vec2 const d=(b-a); // det = 0 (lines are parallel) ll const det=ad*bd; if (det==0) return nullopt; // ld const u=(d*bd)/(ld)det; // ld const v=(d*ad)/(ld)det; Fraction const u=mf(d*bd,det); Fraction const v=mf(d*ad,det); // u < 0 (negative extrapolation) if (signbit(d*bd)!=signbit(det)) return nullopt; if (v<0) return nullopt; // v<0 means lines intersect before ray if (v>1) return nullopt; // v>1 means lines intersect after ray return make_pair(u, det>0); } vector> extrapolate(vec2 s, vec2 t, vector const &h){ vector> events; for (int i=0,j=h.size()-1; i> legal; for (int i=0,j=-1; i> process_edge(vec2 o, vec2 s1, vec2 s2, vec2 t1, vec2 t2) { Fraction first = INT_MAX, last = 0; auto upd = [&](Fraction val) { first = min(val, first); last = max(val, last); }; // inner node on outer edge auto ans1 = line_ray(o,s1,t1,t2-t1); if(ans1) upd(ans1->first); auto ans2 = line_ray(o,s2,t1,t2-t1); if(ans2) upd(ans2->first); // outer node on inner edge auto ans3 = line_ray(o,t1,s1,s2-s1); if(ans3 && ans3->first > 0) upd(inv(ans3->first)); auto ans4 = line_ray(o,t2,s1,s2-s1); if(ans4 && ans4->first > 0) upd(inv(ans4->first)); #ifdef DEBUG cerr<<"- " << evaluate(first) << " - " << evaluate(last) << endl; #endif if (first < last) return {{0, first}, {last, INT_MAX}}; else return {{0, INT_MAX}}; } ll areaX2(vector const &v){ ll total=0; for (int i=0,j=v.size()-1; i>n; vector pa(n); for (auto &i: pa) cin>>i.x>>i.y; int m; cin>>m; vector pb(m); for (auto &i: pb) cin>>i.x>>i.y; if (areaX2(pa)<0) reverse(pa.begin(),pa.end()); if (areaX2(pb)<0) reverse(pb.begin(),pb.end()); vector>> constraints; // For each vertex in A (inner), project outwards for (int i=0; i> events; for (int i=0; i(events.back()) == constraints[i][j].first) get<0>(events.back()) = constraints[i][j].second; else { events.emplace_back(constraints[i][j].first,0,i); events.emplace_back(constraints[i][j].second,1,i); } } } sort(events.begin(),events.end()); ld best=-1L; int satisfied=0; vector active(constraints.size()); for (auto evt: events){ if (satisfied==constraints.size()){ #ifdef USE_FLOATS best=get<0>(evt); #else best=get<0>(evt).evaluate(); #endif } if (get<1>(evt)==0){ ++satisfied; assert(not active[get<2>(evt)]); active[get<2>(evt)]=true; }else{ --satisfied; assert(active[get<2>(evt)]); active[get<2>(evt)]=false; } } cout.precision(20); cout<