游泳水平有限的瑶瑶

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

Problem Description

唉!命运啊!天生聪颖的瑶瑶乘坐的船不幸遇上了风暴,由于年久失修而沉没了。瑶瑶乘着救生艇飘到了一座小岛上。

她飘了一天一夜,又饿又累,这时他发现相邻的一座岛上有果树,于是她决定去那一座岛上摘果子吃。

不幸的是救生艇已经损坏了,他只能靠游泳过去。为了尽量节省体力,tsyao想找一条尽量短的路径游过去。

假设这两座岛都是凸多边形,你能计算出瑶瑶游的最小要距离吗。

Input

第一行一个正整数n,表示第一座岛的顶点个数。

接下来n对顶点按逆时针顺序给出,每两个数 x, y 表示一个顶点的坐标。

然后一个正整数m,表示第二座岛的顶点个数。

接下来m对顶点按逆时针顺序给出,每两个数 x, y 表示一个顶点的坐标。

3 ≤ n,m ≤ 1000

PS: 数据保证给出的两个凸多边形没有重叠

Output

输出最小游泳距离,保留4为小数

Sample Input

3
1 0 0 1 0 0
4
1 1 3 1 3 2 1 2

Sample Output

0.7071

Source

zslzx

Manager

Information
Solved Number328
Submit Number628
Problem Tags
brute force
geometry
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel