#include using namespace std; typedef int64_t ll; typedef long double ld; // O(N^3) //#define USE_FLOATS //#define DEBUG //#define DEBUG_HARDER 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; } ll dot(vec2 const &a)const{ return x*a.x+y*a.y; } ll manhattan()const{ return abs(x)+abs(y); } bool operator<(vec2 const &a)const{ return x!=a.x? x(Fraction const &a)const{ return n*a.d>a.n*d; } Fraction operator+(Fraction const &a)const{ return {n*a.d+a.n*d,d*a.d}; } Fraction operator-(Fraction const &a)const{ return {n*a.d-a.n*d,d*a.d}; } Fraction operator/(Fraction const &a)const{ return Fraction(n*a.d,d*a.n); } explicit operator ld() const{ return n/(ld)d; } }; Fraction mf(ll a,ll b=1){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), true 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 (vmf(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; i0){ Fraction u=mf(h[i].manhattan(),t.manhattan()); Fraction v=mf(h[j].manhattan(),t.manhattan()); if (vj) events.pop_back(); } #ifdef DEBUG_HARDER cerr<<"!! "; for (auto i: events) cerr<<" ("<<(ld)(i.first)<<" | "<> legal; for (int i=0,j=-1; i 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()); // Find interestings direction using the vertices of both shapes. set directions; for (auto const &i: pa){ directions.insert(i.canonical()); } for (auto const &i: pb){ directions.insert(i.canonical()); } // This is the range of sizes that "match", per direction. vector>> constraints; // For each direction, project outwards through both shapes. for (auto const &d: directions){ // O(N+M) #ifdef DEBUG cerr<hi)){ constraints.back().emplace_back(lo,hi); } } #ifdef DEBUG_HARDER cerr<<"constraints: "; for (auto j: constraints.back()){ cerr<<" ["<<(ld)j.first<<" "<<(ld)j.second<<"]"; } cerr<> 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()){ best=(ld)(get<0>(evt)); } 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<