现在的位置: 首页 > 综合 > 正文

Astar 第2题

2012年06月11日 ⁄ 综合 ⁄ 共 509字 ⁄ 字号 评论关闭

篮球场
描述

百度公司有一块长a米宽b米的矩形空地,空地的左上角坐标为(0,0),右下角坐标为(a,b)。空地上长着n株灌木,每株灌木都非常小。现在百度公司准备清理掉其中的一些灌木,在空地上修建两个长28米宽15米的篮球场。

球场必须完全修建在空地内部(边缘可以和空地的边缘重合)且球场边缘必须与空地边缘平行,两个篮球场不允许重叠(不考虑边缘)。

在清理灌木的时候,只有球场内部的灌木需要清理掉,球场外部和边缘的灌木不用清理。请帮助百度公司找到一种球场的建设方案,使得需要清理的灌木最少。

注意:在最优方案中球场的左上角坐标可能是实数。

输入

输入包含多组数据。

每组数据的第一行包含两个整数a、b,表示空地的长和宽。

第二行包含一个整数n,表示空地上灌木的数量。

接下来n行表示所有灌木的坐标,其中第i行包含两个整数xi、yi,表示第i个灌木的坐标为(xi,yi)。

最后一组数据之后的一行为两个0,表示输入结束。
输出

对于每组数据,输出一个整数,表示最少需要清理多少株灌木。
样例输入

50 40

3

11 17

24 26

36 20

0 0

样例输出
1
提示

空地、灌木和最优的球场修建方案如下图所示。

对于100%的数据,30≤ a, b ≤ 100,灌木的坐标都不相同。

抱歉!评论已关闭.