给定平面内平行于坐标轴的一个矩形,从矩形内选择一些点,从这些点向右和向上各射出一条射线,请问:这些射线将矩形分成了多少份。
数据格式:
输入的第一行包含两个整数x, y,表示矩形是由(0, 0), (x, 0), (x, y), (0, y)四个点围成的。
第二行包含一个整数n,表示矩形内的点的数量。
接下来n行,每个两个整数xi, yi,表示矩形内的一个点。输入保证所有的点都在矩形内部而且没有两个点有相同的横坐标或纵坐标。
输出一个整数,表示从给定的点射出的射线将矩形分成的份数。
例如,输入:
10 10
3
1 3
3 1
2 4
程序应该输出:
6
【数据规模和约定】
对于10%的数据,1<=n<=10,1<=x, y<=100;
对于30%的数据,1<=n<=1000,1<=x,y<=1000;
对于60%的数据,1<=n<=10000,1<=x,y<=1000000;
对于100%的数据,1<=n<=100000,1<=x,y<=1000000000,1<xi<x,1<yi<y。
|
|