CS345A1  Red Blue Line Segments
There are n vertical line segments colored red and there are n horizontal line segments colored blue. We wish to find the number of redblue pairs of intersecting segments.
These line segments are inside a unit square. Each blue segment is created by generating 3 random numbers (x_{1}, x_{2}, y) in the interval [0, 1]. These 3 numbers represent the segment joining (x_{1}, y) and (x_{2}, y). Red segments are generated similarly.
Input
First line contains the number of segments n (n ≤ 100000)
next n lines define the blue segments. Each line contains 3 floating point numbers (in [0, 1]) x_{1} x_{2} y representing the segment joining (x_{1}, y) and (x_{2}, y).
next n lines define the red segments. Each line contains 3 floating point numbers (in [0, 1]) y_{1} y_{2} x representing the segment joining (x, y_{1}) and (x, y_{2}).
Output
Print a single line containing the number of intersections.
Note: Touching line segments also count as intersecting. For example  blue segment joining (0.1, 0.2) and (0.3, 0.2) intersects with red segment joining (0.3, 0.4) and (0.3, 0.2).
Example
Input: 3 0.36295 0.557494 0.184032 0.0479258 0.214097 0.508344 0.234284 0.969098 0.739363 0.499323 0.739797 0.138495 0.829265 0.22551 0.290582 0.791082 0.069214 0.450979 Output: 4
hide comments
Christoph Dürr:
20211106 10:52:33
The time limit is too harsh for Python. I have a solution which runs locally in about 2 seconds using pypy on a maximum size instance.


priyankp50:
20150825 22:59:17
no neither red nor blue line should intersect else number of intersecting points would be infinite


Pranjal Shankhdhar:
20150825 18:01:03
@Rishav Most of the guys are of IIT Kanpur. See Resource. 

Rishav Goyal:
20150825 13:32:56
something very strange, > 900 submissions in 3 days :O . /\ :P :P 

beetee:
20150824 08:44:22
So are we supposed to count redred intersection points?


Saurav Shekhar:
20150823 22:42:40
@beetee : Yes, 2 red / blue segments can overlap. 

beetee:
20150823 07:51:26
Is it possible that 2 red lines intersect among themselves? 
Added by:  praveen123 
Date:  20150822 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Algorithms II IIT Kanpur 