/* * Warmup Contest #2, September 4, 2010 Problem F * Solution by Nathaniel Barshay * Originally from http://2008.nwerc.eu/contest/problemset (Problem I) * ACM NWERC 2008 Problem I * * The distance between two polygons is the closest distance between * any pair of lines one of each polygon. (You can visualize this and * prove it to yourself.) * * Nathaniel has good geometry routines here to make his life easy. * */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define IT(c) typeof((c).begin()) #define For(i, a, b) for(int (i) = int(a); i < int(b); ++i) #define rep(x, n) For(x,0,n) #define forit(c, i) for(IT(c) i = (c).begin(); i != (c).end(); ++i) #define bound(num, lower, upper) (max(min((num),((upper)-1)),(lower))) #define debug(x) cerr << #x << " = " << x << "\n" #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define mp make_pair #define setmin(a,b) a=min(a,b) #define setmax(a,b) a=max(a,b) typedef vector vi; typedef vector > vvi; typedef vector vs; typedef pair ii; /*==================================================================================================================*/ int dot(int a[], int b[], int c[]) { int ab[2]; int bc[2]; ab[0] = b[0] - a[0]; ab[1] = b[1] - a[1]; bc[0] = c[0] - b[0]; bc[1] = c[1] - b[1]; return (ab[0]*bc[0])+ (ab[1]*bc[1]); } int cross(int a[], int b[], int c[]) { int ab[2]; int ac[2] ; ab[0] = b[0] - a[0]; ab[1] = b[1] - a[1]; ac[0] = c[0] - a[0]; ac[1] = c[1] - a[1]; return (ab[0]*ac[1]) - (ab[1]*ac[0]); } double dist(int a[], int b[]) { int da=a[0]-b[0]; int db=a[1]-b[1]; return sqrt(da*da+db*db); } double ldist(int a[], int b[], int c[]) { double raw=cross(a,b,c)/dist(a,b); int dott=dot(a,b,c); if(dott>0) return dist(b,c); dott=dot(b,a,c); if(dott>0) return dist(a,c); return abs(raw); } int main() { int np;cin>>np; rep(tp,np) { int n; cin>>n; vector ax; vector ay; rep(i,n) { int t;cin>>t; ax.pb(t); cin>>t; ay.pb(t); } int m;cin>>m; vector bx; vector by; rep(i,m) { int t;cin>>t; bx.pb(t); cin>>t; by.pb(t); } double res=1000000; rep(tt,2) { vector& px=tt?ax:bx; vector& py=tt?ay:by; vector& lx=tt?bx:ax; vector& ly=tt?by:ay; rep(i,sz(px)) { int p[2]; p[0]=px[i]; p[1]=py[i]; rep(k,sz(lx)) { int a[2]; a[0]=lx[k]; a[1]=ly[k]; int b[2]; b[0]=lx[(k+1)%sz(lx)]; b[1]=ly[(k+1)%sz(ly)]; setmin(res, ldist(a,b,p)); } } } cout<