问题 1217 --暴躁的小明

1217: 暴躁的小明

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

题目描述

有一个海报栏,宽度为W,高度为H。海报张贴的时候会按照左下角为原点张贴。
第i张贴上去的海报左下角为(x1_i,y1_i),右上角为(x2_i,y2_i)。
撕去一张海报会导致所有覆盖在其上的海报被同时撕掉(这个过程具有传递性,即如果A覆盖B,B覆盖C,那么撕掉C会导致A和B均被撕掉)
一张海报如果可以被撕掉需要至少存在一个角没有被其他海报覆盖。
海报A被海报B覆盖当且仅当存在A和B的交面积大于0,并且A在B之前贴出。
由于小明是程序员,非常懒,为了提高效率,小明会一次性的撕掉尽可能多的海报。
现在请你帮小明计算小明一次最多可以撕掉多少张海报。
在张数相同的情况下,小明会选择更早贴出的海报。

输入

第一行三个整数W,H,N,分别为海报栏的宽和高,贴出的海报数量。
接下来N行,每行四个整数x1_i,y1_i,x2_i,y2_i。
(1 <= W,H <= 10000000, 1 <= N <= 1000, 0 <= x1_i,x2_i <= W, 0 <= y1_i,y2_i <= H)

输出

输出两个整数,分别是海报数量和撕去的是第几张。

样例输入

6 7 4
0 0 4 4
1 0 3 4
1 4 4 6
0 0 3 5

样例输出

3 1

提示

来源

 

[提交][状态]