描述

在一个有多个发射器使用相同频率进行发送信号的无线网络中，通常要求信号之间不重叠，或者至少不产生冲突。实现这一目标的一种方法是限制发射器的覆盖区域。本题中使用的是一种带屏蔽的发射器，它只会在一个半圆区域内进行广播。

有一个发射器 T 位于一个边长为 $1000$ 米的正方形网格中的某个位置。它的信号覆盖半径为 $r$ 的半圆区域。发射器可以旋转任意角度，但不能移动。给定网格上的 $N$ 个点，计算在发射器信号的覆盖范围内，能够同时被覆盖的点的最大数量。图 1 展示了同一组数据点在发射器不同旋转角度下的情况。

所有输入的坐标均为整数（范围在 $0$ 到 $1000$ 之间）。半径是一个大于 $0$ 的正实数。位于半圆边界上的点被认为是在该半圆区域内。每个发射器需要检查 $1$ 到 $150$ 个不同的点。没有点与发射器处于同一位置。

输入

输入由一个或多个独立的关于发射器问题的信息组成。每个问题的第一行包含发射器的 $(x, y)$ 坐标，紧接着是广播半径 $r$。下一行包含网格上点的数量 $N$，然后是 $N$ 组 $(x, y)$ 坐标，每组坐标占一行。当输入的半径为负数时，表示输入结束；此时 $(x, y)$ 的值虽然存在，但没有实际意义。图 1 和图 2 展示了下面前两个示例数据集的数据，不过它们的比例不同。图 1a 和图 2 展示了能实现最大覆盖范围的发射器旋转角度。

输出

对于每个发射器，输出包含一行，该行内容为在某个半圆区域内能够被包含的点的最大数量。

输入示例

25 25 3.5
7
25 28
23 27
27 27
24 23
26 23
24 29
26 29
350 200 2.0
5
350 202
350 199
350 198
348 200
352 200
995 995 10.0
4
1000 1000
999 998
990 992
1000 999
100 100 -2.5

输出示例

3
4
4

来源

2001 年美国中中部地区竞赛