CS345A1 - Red Blue Line Segments

no tags 

There are n vertical line segments colored red and there are n horizontal line segments colored blue. We wish to find the number of red-blue pairs of intersecting segments.

Red Blue segments in a unit square

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: 2021-11-06 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.
By the way, don't worry too much about overlapping, as the input consists of uniformly drawn random numbers.

priyankp50: 2015-08-25 22:59:17

no neither red nor blue line should intersect else number of intersecting points would be infinite

Pranjal Shankhdhar: 2015-08-25 18:01:03

@Rishav Most of the guys are of IIT Kanpur. See Resource.

Rishav Goyal: 2015-08-25 13:32:56

something very strange, > 900 submissions in 3 days :O . /\ :P :P

beetee: 2015-08-24 08:44:22

So are we supposed to count red-red intersection points?

And how about:
2
0 0.5 0.5
0.5 1 0.5
0 0.5 0.5
0.5 1 0.5

Is this 1 or 4?

Saurav Shekhar: 2015-08-23 22:42:40

@beetee : Yes, 2 red / blue segments can overlap.

beetee: 2015-08-23 07:51:26

Is it possible that 2 red lines intersect among themselves?


Added by:praveen123
Date:2015-08-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Algorithms II IIT Kanpur