#include using namespace std; typedef int64_t ll; typedef long double ld; constexpr ld inf=1e500L; constexpr ll bounds=100000ll; // 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,bool inv){ vector> events; for (int i=0,j=h.size()-1; ifirst=(ans->first+1); #else ans->first.n+=ans->first.d; #endif */ }else{ if (not (ans->first<1)) continue; #ifdef USE_FLOATS ans->first=1/(1-ans->first); #else ans->first.n=ans->first.d-ans->first.n; swap(ans->first.n,ans->first.d); ans->first.simplify(); #endif ans->second=!ans->second; } events.emplace_back(*ans); } } sort(events.begin(),events.end()); #ifdef DEBUG_HARDER cerr<<"!! "; for (auto i: events) cerr<<" ("<> 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, i.x*=bounds, i.y*=bounds; 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 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)==true){ ++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<