#include using namespace std; typedef int64_t ll; typedef long double ld; #define USE_FLOATS #ifdef USE_FLOATS typedef __float128 Fraction; #else struct Fraction{ __int128 n,d; Fraction(ll n=0, ll d=1):n(n),d(d){ if (n) 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),abs(d)); assert(g!=0); n/=g, d/=g; } Fraction operator+(Fraction const &a)const{ return Fraction{n*a.d+a.n*d,d*a.d}; } Fraction operator-(Fraction const &a)const{ return Fraction{n*a.d-a.n*d,d*a.d}; } Fraction operator-()const{ return Fraction{-n,d}; } Fraction &operator+=(Fraction const &a){ n=n*a.d+a.n*a.d; d*=a.d; simplify(); return *this; } Fraction &operator-=(Fraction const &a){ n=n*a.d-a.n*a.d; d*=a.d; simplify(); return *this; } Fraction operator*(Fraction const &a)const{ return {n*a.n,d*a.d}; } Fraction operator/(Fraction const &a)const{ return {n*a.d*(a.n<0?-1:1),d*abs(a.n)}; } Fraction &operator*=(Fraction const &a){ n*=a.n; d*=a.d; simplify(); return *this; } Fraction &operator/=(Fraction const &a){ n*=(a.n<0?-a.d:a.d); d*=abs(a.n); simplify(); return *this; } 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(Fraction const &a)const{ return n*a.d>a.n*d; } bool operator>=(Fraction const &a)const{ return n*a.d>=a.n*d; } bool operator<(ll const &a)const{ return n(ll const &a)const{ return n>a*d; } bool operator<=(ll const &a)const{ return n<=a*d; } bool operator>=(ll const &a)const{ return n>=a*d; } bool operator==(ll const &a)const{ return n==a*d; } ld evaluate() const{ return n/(ld)d; } explicit operator ll() const{ assert(d==1); return n; } explicit operator ld() const{ return evaluate(); } }; #endif struct vec2{ Fraction x,y; vec2 operator-(vec2 const &a)const{ return {x-a.x,y-a.y}; } vec2 operator -()const{ return {-x,-y}; } vec2 operator *(Fraction const f)const{ return {x*y,y*f}; }; vec2 &operator *=(Fraction const f){ x*=f; y*=f; return *this; } Fraction operator ^(vec2 const &a)const{ return (y*a.x)-(x*a.y); } }; ll areaX2(vector const &v){ Fraction total=0; for (int i=0,j=v.size()-1; i find_intersections(vec2 const &v,vector const &b){ vector res; for (int i=0,j=b.size()-1; i!=b.size(); j=i++){ if ((v^b[i])*(v^b[j])<=0){ vec2 b1=b[i]; vec2 bd=b[j]-b[i]; if ((bd^v)==0) continue; // v*f = b1 + bd*g // vx*f = b1x + bdx*g // vy*f = b1y + bdy*g // // bdy*vx*f - bdx*vy*f = b1x*bdy - b1y*bdx // (bd^v)*f = (bd^b) // f = (bd^b1)/(bd^v) Fraction f = (bd^b1)/(bd^v); if (f==0){ continue; } if (f>0){ res.push_back(f); } } } return res; } Fraction interpolate(vec2 a,vec2 b,Fraction x){ vec2 ab=(b-a); return a.y+ab.y*(x-a.x)/ab.x; } vector> vertical_slice(vector const &p,Fraction const x){ vector opens,closes; for (int c=0,b=p.size()-1,a=p.size()-2; cx){ // going left = roof closes.push_back(interpolate(p[a],p[b],x)); } } else if (p[b].x>x){ if (p[a].xx and p[c].x>x) or (p[a].xp[b].y and p[b].x>p[a].x){ // transition up wall from floor opens.push_back(p[b].y); } } else if (p[a].x==x){ // end of a vertical segment if (p[a].yp[b].y and p[c].x>p[b].x){ // transition from down wall to floor opens.push_back(p[b].y); } } else if (p[a].x>x and p[c].xx){ // going right = ground opens.push_back(p[b].y); } } } sort(opens.begin(),opens.end()); sort(closes.begin(),closes.end()); assert(opens.size()==closes.size()); vector> regions; for (int i=0,j=1; i const &a,vector const &b,bool plog){ vector key_x; for (auto i: a) key_x.push_back(i.x); for (auto i: b) key_x.push_back(i.x); sort(key_x.begin(),key_x.end()); for (int i=key_x.size()-1; i-->0;) key_x.push_back((key_x[i]+key_x[i+1])/2.0L); sort(key_x.begin(),key_x.end()); Fraction lx{-1}; for (auto const &x: key_x){ if (x==lx) continue; else lx=x; vector> outer=vertical_slice(b,x); vector> inner=vertical_slice(a,x); if (plog){ cerr<<" consider "<<(long double)(x)<inner[i].first or outer[j].second>n; vector pa(n); for (auto &i: pa) {long double x,y; cin>>x>>y; i={x,y};} int m; cin>>m; vector pb(m); for (auto &i: pb) {long double x,y; cin>>x>>y; i={x,y};} if (areaX2(pa)<0) reverse(pa.begin(),pa.end()); if (areaX2(pb)<0) reverse(pb.begin(),pb.end()); // Compute the scaling factors at which a vertex of one shape touches // an edge of another shape. vector boundaries; for (int i=0; i pa2=pa; for (auto &i: pa2) i*=sf; bool plog=(abs((ld)(sf)-2.4921793253597721482)<1e-10L); if (plog) cerr<<"trying "<<(long double)(sf)<