相交问题
问题描述
一个二维平面上有若干矩形,以及一条线段。线段可能穿过某些矩形。你的任务是统计线段穿过的矩形数目。
一条线段穿过一个矩形是指,线段和具有公共部分 ,哪怕仅仅是一个点。例如,一个矩形(0,0),(0,1),(1,1),(1,0),则线段(-1,-1)-(2,2),穿过该矩形,线段(0,-1)-(2,1)穿过该矩形,线段(1,-1)-(3,1)不穿过该矩形。
输入格式
输入文件的第一行是一个整数n(n≤10 000),表示矩形的个数。
第二行有4个整数x0,y0,x1,y1,中间用一个空格隔开,描述一条线段(x0,y0),和 (x1,y1)分别表示矩形的左下角和右上角。
所有的坐标都在-20 000到20 000之间。
输出格式
输出文件至于一个整数,表示与线段相交的矩形数。
输入样例
1
0 0 5 5
0 1 6 6
输出样例
1
信息
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者