TopCoder MSRM 485 Deposit

时间限制:5s      空间限制:128MB

题目描述

从前,森林里有一只脑子进水的兔子。

它平时搞OI,做题做累了就开始在森林里探险。

兔子的探险在森林里进行,森林可以视为一个凸多边形区域。森林中,有一块同样为凸多边形的宝地,种满了萝卜!!!

兔子的游戏很哲学,游戏过程是这样的,兔子从森林的边缘随机选一个起点,然后选择森林边缘上离起点最远的点做终点(如果有多个点,那么等概率选择其中一个),兔子会从起点开始,沿直线一路跑到终点,如果奔跑的过程中,它路过了萝卜地,那么兔子觉得这个起点是一个幸运点,否则,兔子认为这个起点是没有意义的。现在兔子想知道,它选到幸运点的概率是多少。


输入格式

输入文件第一行包含两个整数NM,表示森林边缘的点数和萝卜地边缘的点数。

第二行和第三行,以逆时针顺序给出森林。第二行N个整数,表示N点的x坐标,第三行给出N个相应的y坐标。

第四行和第五行,以逆时针顺序给出萝卜地。第四行M个整数,表示M个点的x坐标,第五行给出M个相应的y坐标。


输出格式

输出文件仅包含一个数,既兔子取到幸运点的概率,四舍五入保留9位小数。


样例输入

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

样例输出

0.666666667

提示

 对于100%的数据,有3 ≤ N,M ≤ 50。坐标绝对值不超过1000。


题目来源

2011福建集训