您所在位置：主题：一个ACM题，对时间要求比较高
budognai
[专家分：0] 发布于 2007-10-12 21:05:00
题目的大体意思是这样的：
在平面内，给出N个线段，不是垂直的就是水平的，而且没有任意一条线段长度为零，问题是求出所有的交点
Line-Segment Intersection
--------------------------------------------------------------------------------
Time limit: 3sec. Submitted: 102
Memory limit: 64M Accepted: 21
Source : seeman
--------------------------------------------------------------------------------
A number of line segments are pasted on a huge wall. They are either vertical or horizontal. Your job is to calculate the number of the points that every vertical line segment intersects the horizontal line segments and print the sum of them.
Input
Input will consist of multiple input sets. Each set will start with a single line containing a positive integer n indicating the total number of line segments on the huge wall. Each of the next n lines will contain a description of one segment in the format
x1 y1 x2 y2
where (x1,y1) are the coordinates of one endpoint and (x2,y2) are the coordinates of the other. Coordinate values are integer point values in the range -109...109. The maximum number of line segments will be 105 and all segments will have non-zero length. Following the last input set there will be a line containing a 0 indicating end of input; it should not be processed.
Output
For each input set, output on a single line the sum of points that every vertical line segment intersects the horizontal line segments.
Sample Input
7
1 1 10 1
7 1 16 1
5 2 22 2
5 -2 8 -2
8 -1 8 7
16 1 16 6
10 -1 10 -7
0
Sample Output
5
在平面内，给出N个线段，不是垂直的就是水平的，而且没有任意一条线段长度为零，问题是求出所有的交点
Line-Segment Intersection
--------------------------------------------------------------------------------
Time limit: 3sec. Submitted: 102
Memory limit: 64M Accepted: 21
Source : seeman
--------------------------------------------------------------------------------
A number of line segments are pasted on a huge wall. They are either vertical or horizontal. Your job is to calculate the number of the points that every vertical line segment intersects the horizontal line segments and print the sum of them.
Input
Input will consist of multiple input sets. Each set will start with a single line containing a positive integer n indicating the total number of line segments on the huge wall. Each of the next n lines will contain a description of one segment in the format
x1 y1 x2 y2
where (x1,y1) are the coordinates of one endpoint and (x2,y2) are the coordinates of the other. Coordinate values are integer point values in the range -109...109. The maximum number of line segments will be 105 and all segments will have non-zero length. Following the last input set there will be a line containing a 0 indicating end of input; it should not be processed.
Output
For each input set, output on a single line the sum of points that every vertical line segment intersects the horizontal line segments.
Sample Input
7
1 1 10 1
7 1 16 1
5 2 22 2
5 -2 8 -2
8 -1 8 7
16 1 16 6
10 -1 10 -7
0
Sample Output
5