2254. Line Segments

单点时限: 10.0 sec

内存限制: 256 MB

Line segments are a very common element in computational geometry. A line segment is the set of points forming the shortest path between two points (including those points). Although they are a very basic concept it can be hard to work with them if they appear in huge numbers unless you have an efficient algorithm.

Given a set of line segments, count how many distinct pairs of line segments are overlapping. Two line segments are said to be overlapping if they intersect in an infinite number of points.

输入格式

The first line contains the number of scenarios.

Each scenario starts with the number n of line segments (1 <= n <= 100000). Then follow n lines consisting of four integers x1, y1, x2, y2 in the range [0, 1000000] each, representing a line segment that connects the points (x1, y1) and (x2, y2). It is guaranteed that a line segment does not degenerate to a single point.

输出格式

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the number of distinct pairs of overlapping line segments followed by an empty line.

样例

Input
2
8
1 1 2 2
2 2 3 3
1 3 3 1
10 0 20 0
20 0 30 0
15 0 25 0
50 0 100 0
70 0 80 0
1
0 0 1 1
Output
Scenario #1:
3
Scenario #2:
0
Hint:
Huge input,scanf is recommended.

提示

The number of overlapping pairs may not fit into a 32-bit integer.

Huge input,scanf is recommended.

1 人解决,2 人已尝试。

2 份提交通过,共有 7 份提交。

9.8 EMB 奖励。

创建: 15 年,3 月前.

修改: 2 年,4 月前.

最后提交: 2 年,4 月前.

来源: TUD Programming Contest 2005, Darmstadt, Germany

题目标签