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 mp make_pair
#define pb push_back

typedef long double db;

template<class T> inline void cmin(T&x,T c){if(c<x)x=c;}
template<class T> inline void cmax(T&x,T c){if(c>x)x=c;}
 
const db EPS = 1e-8;
 
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 P(x + p.x, y + p.y); }
    P operator-(P p) { return P(x - p.x, y - p.y); }
    P operator*(db d) { return P(x * d, y * d); }
    P operator/(db d) { return P(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;
    }
    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; }
    db abs() { return sqrt(abs2());}
    db abs2() { return x * x + y * y; }
    P rot90() { return P(-y,x);}
    P unit() { return *this/abs(); }
};
 
#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))

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 crsLL(P p1, P p2, P q1, P q2){
    db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return sign(a1+a2) != 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);
}

P vs,vt;
int N,M;
vector<P> W,E;

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;
}

bool check(vector<P> ps, P s, P t){
	vector<P> important;
	int n=ps.size();

	rep(i,0,n){
		P p1=ps[i],p2=ps[(i+1)%n];
		if(crsLL(p1,p2,s,t)){
			P q = isLL(p1,p2,s,t);
			if(isMiddle(s,q,t))
				important.pb(q);
		}
	}
	important.pb(s);
	important.pb(t);
	sort(important.begin(), important.end());

	rep(i,0,important.size() - 1){
		if((important[i] - important[i+1]).abs() > EPS){
			P p = (important[i] + important[i+1])/2;
			if(contain(ps,p) == 0) return 0;
		}
	}

	return 1;
}

db dijstra(vector<P> ps, P s, P t,int tp){

	static bool first[2] = {1,1};
	static bool can[2][30][30] = {};
	static db edge[2][30][30];

	vector<P> qs = ps;

	qs.pb(s);qs.pb(t);

	int n = qs.size();

	if(first[tp]){
		rep(i,0,n) rep(j,0,i){
			can[tp][i][j] = can[tp][j][i] = check(ps,qs[i],qs[j]);
			edge[tp][i][j] = edge[tp][j][i] = (qs[i] - qs[j]).abs();
		}
		first[tp] = 0;
	} else {
		rep(i,n-2,n) rep(j,0,i){
			can[tp][i][j] = can[tp][j][i] = check(ps,qs[i],qs[j]);
			edge[tp][i][j] = edge[tp][j][i] = (qs[i] - qs[j]).abs();
		}
	}

	db dist[30] = {};
	bool used[30] = {};
	rep(i,0,n) dist[i] = 1e100;

	dist[n-2] = 0;

	rep(i,0,n){
		int u = -1;
		rep(i,0,n) if(!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
		used[u] = 1;
		rep(i,0,n) if(can[tp][u][i]){
			cmin(dist[i],dist[u] + edge[tp][u][i]);
		}
	}

	return dist[n-1];
} 


P proj(P p1, P p2, P q) {
    P dir = p2 - p1;
    return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}

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));
}

P nearestP(P p1,P p2,P q){
    P h = proj(p1,p2,q);
    if(isMiddle(p1,h,p2))
        return h;
    if(p1.distTo(q) < p2.distTo(q))
    	return p1;
    else
    	return p2;
}

db bridge,total;

void update(db br,db tot){
	if(abs(br-bridge) <= 1e-14){
		cmin(total,tot);
		return;
	}
	if(br < bridge){
		bridge = br;
		total = tot;
	}
}

P getP(P st, P dir, db dt){
	return st + dir * (dt - st.dot(dir));
}

void solve(P w1,P w2,P e1,P e2){
	// w1 -- w2
	// e1 -- e2

	//four cases
	rep(i,0,2){
		P me = i?w2:w1;
		P p = nearestP(e1,e2,me);
		update(p.distTo(me), dijstra(W,vs,me,0) + dijstra(E,p,vt,1));
	}

	rep(i,0,2){
		P me = i?e2:e1;
		P p = nearestP(w1,w2,me);
		update(p.distTo(me), dijstra(W,vs,p,0) + dijstra(E,me,vt,1));
	}

	//a special case
	if(sign((w2-w1).det(e2-e1)) == 0){
		P dir = (e2-e1).unit();
		if(w2.dot(dir) < w1.dot(dir)) swap(w1,w2);

		db l = max(e1.dot(dir),w1.dot(dir));
		db r = min(e2.dot(dir),w2.dot(dir));

		if(cmp(l,r) >= 0) return;

		db ret = getP(w1,dir,l).distTo(getP(e1,dir,l));

		if(ret > bridge + 1e-14) return;

		auto calc = [w1,e1,dir](db x){
			P pW = getP(w1,dir,x);
			P pE = getP(e1,dir,x);
			return dijstra(W,vs,pW,0) + dijstra(E,pE,vt,1);
		};

		rep(it,0,60){
			db L = (l*2+r)/3, R = (l+2*r)/3;

			if(calc(L) < calc(R))
				r=R;
			else
				l=L;
		}

		update(ret, calc(l));
	}
}

int main(){
	vs.read();vt.read();
	cin>>N; W.resize(N); rep(i,0,N) W[i].read(); W.pb({0,1000}); W.pb({0,0});


	cin>>M; E.resize(M); rep(i,0,M) E[i].read(); E.pb({1000,1000}); E.pb({1000,0});

	bridge = 1e100; total = 1e100;

	rep(i,0,W.size()) rep(j,0,E.size()) solve(W[i],W[(i+1)%W.size()],E[j],E[(j+1)%E.size()]);

	printf("%0.10f %0.10f\n", (double)bridge, (double)(bridge + total));
}