P2861 [USACO06JAN] Roping the Field G

题目描述

约翰真是一个自然派艺术大师,他常常在他的田地上创作一些巨大的艺术杰作。今天,他想在麦田上创作一幅由绳索构成的巨画。他的麦田是一个多边形,由 $N\ (1 \le N \le 150)$ 个篱笆粧和之间的篱笆围成。为了创作他的巨画,他打算用尽量多的数量的绳索,笔直地连接两个不相邻的篱笆粧。但是为了画作的优美,任意两根绳索不得交叉。 约翰有一个难处:一些邪恶的外星人在他的麦田上整出了 $G\ (0 \le G \le 100)$ 个怪圈。这些怪圈都有一定的半径 $R\ (1\le R\le 100000)$。他不敢惹外星人,所以不想有任何绳索通过这些怪圈,即使碰到怪圈的边际也不行。这些怪圈的圆心都在麦田之内,但一些怪圈可能有部分在麦田之外。一些篱笆或者篱笆粧都有可能在某一个怪圈里。 给出篱笆粧和怪圈的坐标,计算最多的绳索数。所有的坐标都是 $[0,10^6]$ 内的整数。

输入格式

第 $1$ 行输入三个整数 $N,G,R$。 接下来 $N$ 行,每行输入两个整数表示篱笆粧的坐标。 接下来 $G$ 行,每行输入两个整数表示一个怪圈的圆心坐标。

输出格式

一行一个正整数表示答案。

说明/提示

样例解释:唯一一条绳索连接了 $(10,7)$ 和 $(2,0)$。