编程介的小学生 2016-12-16 15:30 采纳率: 20.5%
浏览 1025
已采纳

Line Segments

Description

Background
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.
Problem
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.
Input

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.
Output

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.
Hint: The number of overlapping pairs may not fit into a 32-bit integer.
Sample 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
Sample Output

Scenario #1:
3

Scenario #2:
0

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-16 15:41
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致