问题 E: 奇妙的图案

问题 E: 奇妙的图案

时间限制: 1 Sec  内存限制: 128 MB
提交: 14  解决: 0
[状态] [讨论版] [提交] [命题人:]
题目描述

最近,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≤ 100,000     0≤ 所有坐标XY100,000

样例输入 Copy
5 3 1
6 10
10 7
9 1
2 0
0 3
2 2
5 6
8 3
样例输出 Copy
1