5/9/25, 8:50 PM SPOJ.
com - Problem CS345A1
(/)
Problems (/problems) / classical (/problems/classical) / Red Blue Line Segments
My status (/status/CS345A1,iloveht/) Status (/status/CS345A1/) Ranking (/ranks/CS345A1/)
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.
These line segments are inside a unit square. Each blue segment is created by generating
3 random numbers (x1, x2, y) in the interval [0, 1]. These 3 numbers represent the
segment joining (x1, y) and (x2, 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]) x1 x2 y representing the segment joining (x1, y) and (x2, y).
next n lines define the red segments. Each line contains 3 floating point numbers (in [0, 1])
y1 y2 x representing the segment joining (x, y1) and (x, y2).
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).
https://www.spoj.com/problems/CS345A1/ 1/4
5/9/25, 8:50 PM SPOJ.com - Problem CS345A1
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
Submit solution! (/submit/CS345A1/)
hide comments
Christoph Dürr (/users/xtof_durr): 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 (/users/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 (/users/evil999man): 2015-08-25 18:01:03
@Rishav Most of the guys are of IIT Kanpur. See Resource.
Rishav Goyal (/users/sherlock_holms): 2015-08-25 13:32:56
something very strange, > 900 submissions in 3 days :O . /\ :P :P
beetee (/users/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 (/users/sshekh): 2015-08-23 22:42:40
@beetee : Yes, 2 red / blue segments can overlap.
beetee (/users/beetee): 2015-08-23 07:51:26
Is it possible that 2 red lines intersect among themselves?
Leave a Comment
https://www.spoj.com/problems/CS345A1/ 2/4
5/9/25, 8:50 PM SPOJ.com - Problem CS345A1
Publish
Notes:
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our forum (/forum).
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to
provide some useful links).
Submit solution! (/submit/CS345A1/)
Added by: praveen123 (/users/dhinwa123)
Date: 2015-08-22
Time limit: 2s
Source
50000B
limit:
Memory
1536MB
limit:
Cluster: Cube (Intel G860) (/clusters/)
Languages: All except: ASM64 GOSU JS-MONKEY
Algorithms II IIT Kanpur
Resource:
(http://cse.iitk.ac.in/pages/CS345.html)
Vote requirements
be spoj user for at least 5 days
https://www.spoj.com/problems/CS345A1/ 3/4
5/9/25, 8:50 PM SPOJ.com - Problem CS345A1
solved 6 from 15 needed problems
solve this problem
Own tags
# #
Tag name Add
About (/info) | Tutorial (/tutorials) | Tools (/tools) | Clusters (/clusters) | Credits (/credits) | API
(/sphereengine) | Widgets (/sphereengine-widget)
Legal: Terms of Service (/legal-tos/) | Privacy Policy (/legal-pp/) | GDPR Info (/legal-gdpr/)
RSS (/rss/)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine (http://sphere-engine.com?
utm_campaign=permanent&utm_medium=footer&utm_source=spoj)™ © by Sphere Research Labs
(http://sphere-research.com?utm_campaign=permanent&utm_medium=footer&utm_source=spoj).
https://www.spoj.com/problems/CS345A1/ 4/4
