最近,Dr. Kong对几何图形发生了浓厚的兴趣。他发现在一个凸多边形里随意加上几个等半径的圆,再将圆涂成不同的颜色,就能构造出一幅美妙的图案。进而,Dr. Kong大发灵感,在此图案的基础上,又加入了几条连接凸多边形的两个不相邻顶点的直线,图形更加奇妙。
这时,Dr. Kong遇到了一个问题,他不想让加入的直线相互交叉,也不想让加入的直线穿过凸多边形里的任何一个圆,甚至不能与任何圆相切。
已经知道凸多边形的N个顶点的坐标,也知道了其中M个圆的圆心坐标和半径R。你能帮助Dr. Kong计算出可加上的满足所有条件的最多直线数吗?
第1行: N M R 三个正整数
接下来有N行, 每一行为凸多边形一个坐标TXi TYi (i=1,…,N)
再接下来有M行,每一行为一个圆的圆心坐标PXj PYj (j=1,…,M)
输出有一个整数, 表示可加上的最多直线数。
5≤ N ≤150 0≤ M ≤100 1≤ R ≤100,000 0≤ 所有坐标X,Y≤100,000
5 3 1
6 10
10 7
9 1
2 0
0 3
2 2
5 6
8 3
1