Non-intersecting Segments
Practice
3.8 (33 votes)
Algorithms
Dynamic programming
Easy
Problem
89% Success 10247 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

There are two different parallel lines $$L_1$$ and $$L_2$$ and there are $$N$$ segments connecting them. Each segment connects two points $$(x_i, y_i)$$ and $$(x'_i, y'_i)$$ from these lines. You can assume that all the points $$(x_i, y_i)$$ belong to $$L_1$$ and all the points $$(x'_i, y'_i)$$ belong to $$L_2$$.
Your task is to find a subset of these segments such that there won’t be any two segments crossing each other. It is guaranteed that all the given points have distinct coordinates.

Input Format
The first line contains an integer $$N$$, the number of segments $$(1 \leq N \leq 10^5)$$. 
Each of the next $$N$$ lines contain \(4\) space-separated integers $$x_i, y_i, x'_i, y'_i$$ - each describing the endpoints of a segment $$(-10^9 \leq x_i, y_i, x'_i, y'_i \leq 10^9)$$. 

Output Format
Print the maximum number of segments such that there won’t be any two of them crossing each other.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
33 votes
Tags:
Easy
Points:30
7 votes
Tags:
CombinatoricsDynamic ProgrammingAlgorithmsStringIntroduction to Dynamic Programming 1
Points:30
500 votes
Tags:
Dynamic ProgrammingEasy