问题1054--矩形覆盖

1054: 矩形覆盖

时间限制: 1 Sec  内存限制: 128 MB
提交: 58  解决: 24
[提交] [状态] [讨论版] [命题人:]

题目描述

学校门口路面上出现了一个矩形大洞。现在学校找来了一些矩形钢板,想要盖住这个大洞。可是,他们又想不出一个既安全又节省的覆盖方案,所以,找到了参加程序设计竞赛的你,帮忙设计一个覆盖方案。

       从安全角度考虑,钢板的放置必须符合如下所有原则:

1.       钢板之间可以相互叠加。

2.       钢板必须完全覆盖大洞。

3.       你可以任意旋转每块钢板,但是覆盖过程中,钢板的边必须与大洞的边平行。

4.       每块钢板的4个角必须严格落在大洞外(钢板任何一个角和洞口的角重合,或者在大洞内部,这块钢板就会不稳定)

如下图所示几种放置方法,黑色表示大洞区域,红色表示钢板:

AB中,都有钢板的点在大洞内部,不能这样放置。图CD中,钢板4个角都在大洞外,是稳定安全的。图E中,也是不稳定的,就算钢板的角在其他钢板上,也要落在大洞外。

请问能否在安全的前提下,用这些钢板盖住这个大洞,若可以,使用最少的钢板数量进行覆盖。请你帮忙计算一下!

输入

第一行两个整数RC,表示大洞的长和宽。

第二行一个整数N,表示矩形钢板数量

接下来N行,每行两个整数w[i]h[i],表示第i块钢板的长和宽。

输出

要覆盖大洞最少使用钢板的数量,若无法覆盖,输出-1.

样例输入 Copy

5 5
3
8 2
8 3
8 4

样例输出 Copy

2

提示

【样例1解释】

任意选择两个钢板就可以盖住这个大洞。例如用最小的两个(8,2)和(8,3)钢板刚好覆盖如下图:

【输入输出样例2

cover.in

cover.out

10 10

4

6 6

6 6

6 6

6 6

-1

【样例2解释】

无法覆盖,任何一个钢板都无法放上去。无法使钢板的四个角都落在大洞外。

 

【数据范围】

30%的数据,1<=R,C<=10001<=w[i]<=1000,h[i]=1

70%的数据,n<=20,1<=R,C<=10001<=w[i],h[i]<=1000

100%的数据1<=n<=501<=R,C,w[i],h[i]<=1000000000

来源/分类