Problem: Example

Input

200 500 800 500
3
400 0
450 500
400 1000
3
600 0
550 500
600 1000


Output

100 600

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

typedef long double db;
const db EPS = 1e-13;

inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }

inline int cmp(db a, db b){ return sign(a-b); }

struct P {
	db x, y;
	P() {}
	P(db _x, db _y) : x(_x), y(_y) {}
	P operator+(P p) { return {x + p.x, y + p.y}; }
	P operator-(P p) { return {x - p.x, y - p.y}; }
	P operator*(db d) { return {x * d, y * d}; }
	P operator/(db d) { return {x / d, y / d}; }
 
	bool operator<(P p) const { 
		int c = cmp(x, p.x);
		if (c) return c == -1;
		return cmp(y, p.y) == -1;
	}
 
	bool operator==(P o) const{
		return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
	}
 
	db dot(P p) { return x * p.x + y * p.y; }
	db det(P p) { return x * p.y - y * p.x; }
	 
	db distTo(P p) { return (*this-p).abs(); }
	db alpha() { return atan2(y, x); }
	void read() { cin>>x>>y; }
	void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
	db abs() { return sqrt(abs2());}
	db abs2() { return x * x + y * y; }
	P rot90() { return P(-y,x);}
	P unit() { return *this/abs(); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	P rot(db an){ return {x*cos(an)-y*sin(an),x*sin(an) + y*cos(an)}; }
};
 
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
  
bool chkLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return sign(a1+a2) != 0;
}
 
P isLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}
  
  
bool intersect(db l1,db r1,db l2,db r2){
	if(l1>r1) swap(l1,r1); if(l2>r2) swap(l2,r2); 
	return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
  
bool isSS(P p1, P p2, P q1, P q2){
	return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) && 
	crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) <= 0;
}
  
bool isSS_strict(P p1, P p2, P q1, P q2){
	return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) < 0;
}
  
bool isMiddle(db a, db m, db b) {
	return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
  
bool isMiddle(P a, P m, P b) {
	return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
  
bool onSeg(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
 
bool onSeg_strict(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
  
P proj(P p1, P p2, P q) {
	P dir = p2 - p1;
	return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
  
P reflect(P p1, P p2, P q){
	return proj(p1,p2,q) * 2 - q;
}
  
db nearest(P p1,P p2,P q){
	P h = proj(p1,p2,q);
	if(isMiddle(p1,h,p2))
		return q.distTo(h);
	return min(p1.distTo(q),p2.distTo(q));
}
  
db disSS(P p1, P p2, P q1, P q2){
	if(isSS(p1,p2,q1,q2)) return 0;
	return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}

int contain(vector<P> ps, P p){ //2:inside,1:on_seg,0:outside
	int n = ps.size(), ret = 0; 
	rep(i,0,n){
		P u=ps[i],v=ps[(i+1)%n];
		if(onSeg(u,v,p)) return 1;
		if(cmp(u.y,v.y)<=0) swap(u,v);
		if(cmp(p.y,u.y) >0 || cmp(p.y,v.y) <= 0) continue;
		ret ^= crossOp(p,u,v) > 0;
	}
	return ret*2;
}

const int N=30;
P s,t;
vector<P> p,q;
db r1,r2,dis[N][N],diss[N];
int n,m,g[2][N][N],vis[N];

bool valid(vector<P> p,P s,P t) {
	int n=SZ(p);
	rep(i,0,n) if (isSS_strict(p[i],p[(i+1)%n],s,t)) return 0;
	vector<P> cand; cand.pb(s); cand.pb(t);
	rep(i,0,n) if (onSeg(s,t,p[i])) cand.pb(p[i]);
	sort(all(cand));
	cand.erase(unique(all(cand)),cand.end());
	rep(i,0,SZ(cand)-1) {
		P md=(cand[i]+cand[i+1])*0.5;
		if (contain(p,md)==0) return 0;
	}
	return 1;
}
db gao(vector<P> p,int d,P s,P t) {
	vector<P> q; q=p; q.pb(s); q.pb(t);
	int n=SZ(p);
	rep(i,0,n+2) rep(j,0,n+2) dis[i][j]=(i==j)?0:1e10;
	rep(i,0,n+2) rep(j,i+1,n+2) {
		if (i<n&&j<n) {
			if (g[d][i][j]) dis[i][j]=dis[j][i]=q[i].distTo(q[j]);
		} else if (valid(p,q[i],q[j])) dis[i][j]=dis[j][i]=q[i].distTo(q[j]);
	}
	n+=2;
	rep(i,0,n) diss[i]=1e30,vis[i]=0; diss[n-2]=0;
	rep(i,0,n) {
		int minp=-1; db minv=1e30;
		rep(j,0,n) if (diss[j]<minv&&!vis[j]) minv=diss[j],minp=j;
		vis[minp]=1;
		rep(j,0,n) diss[j]=min(diss[j],diss[minp]+dis[minp][j]);
	}
	return diss[n-1];
}

int main() {
	s.read(); t.read();
	scanf("%d",&n); n+=2;
	p.resize(n); p[0]=P(0,0); p[n-1]=P(0,1000);
	rep(i,1,n-1)  p[i].read();
	scanf("%d",&m); m+=2;
	q.resize(m); q[0]=P(1000,0); q[m-1]=P(1000,1000);
	rep(i,1,m-1) q[i].read();
	rep(i,0,n) rep(j,i,n) g[0][i][j]=g[0][j][i]=valid(p,p[i],p[j]);
	rep(i,0,m) rep(j,i,m) g[1][i][j]=g[1][j][i]=valid(q,q[i],q[j]);
	db r1=1e30,r2=1e30;
	rep(i,1,n-2) rep(j,1,m-2) r1=min(r1,disSS(p[i],p[i+1],q[j],q[j+1]));
	rep(i,1,n-1) rep(j,1,m-1) {
		db d1=p[i].distTo(q[j]);
		if (cmp(d1,r1)==0) {
			r2=min(r2,gao(p,0,s,p[i])+gao(q,1,t,q[j]));
		}
		if (j<m-2) {
			d1=nearest(q[j],q[j+1],p[i]);
			if (cmp(d1,r1)==0) {
				P r=proj(q[j],q[j+1],p[i]);
				if (isMiddle(q[j],r,q[j+1])) r2=min(r2,gao(p,0,s,p[i])+gao(q,1,t,r));
			}
		}
		if (i<n-2) {
			d1=nearest(p[i],p[i+1],q[j]);
			if (cmp(d1,r1)==0) {
				P r=proj(p[i],p[i+1],q[j]);
				if (isMiddle(p[i],r,p[i+1])) r2=min(r2,gao(p,0,s,r)+gao(q,1,t,q[j]));
			}
		}
	}
	rep(i,1,n-2) rep(j,1,m-2) {
		db d1=disSS(p[i],p[i+1],q[j],q[j+1]);
		if (cmp(d1,r1)>0) continue;
		if (sign((p[i+1]-p[i]).det(q[j+1]-q[j]))!=0) continue;
		P pl=p[i],pr=p[i+1];
		if (!isMiddle(q[j],proj(q[j],q[j+1],pl),q[j+1])) pl=proj(p[i],p[i+1],q[j]);
		if (!isMiddle(q[j],proj(q[j],q[j+1],pr),q[j+1])) pr=proj(p[i],p[i+1],q[j+1]);
		if (!isMiddle(p[i],pl,p[i+1])||!isMiddle(p[i],pr,p[i+1])) continue;
		rep(it,0,40) {
			P fl=(pl+pl+pr)/3,fr=(pl+pr+pr)/3;
			db vl=gao(p,0,s,fl)+gao(q,1,proj(q[j],q[j+1],fl),t);
			db vr=gao(p,0,s,fr)+gao(q,1,proj(q[j],q[j+1],fr),t);
			r2=min(r2,min(vl,vr));
			if (vl>vr) pl=fl; else pr=fr;
		}
	}
	printf("%.10f %.10f\n",(double)r1,(double)(r1+r2));
}