{"id":2368,"date":"2020-07-29T07:34:12","date_gmt":"2020-07-29T07:34:12","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2368"},"modified":"2022-03-31T12:16:25","modified_gmt":"2022-03-31T12:16:25","slug":"points-collisionpaid","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/points-collisionpaid\/","title":{"rendered":"Points Collision"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Computational geometry.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

A segment of line is defined as the line connecting two points in the Cartesian Coordinate System. The segments are defined by start and end points
\n(Xi,Yi) and (Xj,Yj) (1<=i,j<=n). Coordinates of these points are integer numbers with real value smaller than 1000
\n. Length of each segment is positive.
\nWhen 2 segments don't have a common point then it is said that segments don't collide. In anyother case segments collide. Be aware that segments collide even if they have only one point in common.Segment is said to be isolated if it doesn't collide with all the other segments that are given, i.e.segmenti is isolated when for each 1<=j<=n (i!=j), segments i and j don't collide. You are asked to find number T – How many segments are isolated.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
Input\n3\n3\n0 0 2 0\n1 -1 1 1\n2 2 3 3\n2\n0 0 1 1\n1 0 0 1\n2\n0 0 0 1\n0 2 0 3\n\nOutput\n1\n0\n2<\/code><\/pre>\n
BRUTE FORCE:<\/h3>\n
\n
Naive Algorithm A naive solution to solve this problem is to check every pair of lines and check if the pair intersects or not. We can check two line segments in O(1) time. Therefore, this approach takes O(n*n).<\/p>\n<\/blockquote>\n
Sweep Line Algorithm:<\/h3>\n
\n
We can solve this problem in O(nLogn) time using Sweep Line Algorithm. The algorithm first sorts the end points along the x axis from left to right, then it passes a vertical line through all points from left to right and checks for intersections. Following are detailed steps.<\/p>\n
    \n
  1. \n
    Let there be n given lines. There must be 2n end points to represent the n lines. Sort all points according to x coordinates. While sorting maintain a flag to indicate whether this point is left point of its line or right point.<\/p>\n<\/li>\n
  2. \n
    Start from the leftmost point. Do following for every point<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    a.If the current point is a left point of its line segment, check for intersection of its line segment with the segments just above and below it. And add its line to active line segments (line segments for which left end point is seen, but right end point is not seen yet).  Note that we consider only those neighbors which are still active.<\/p>\n
    b.If the current point is a right point, remove its line segment from active list and check whether its two active neighbors (points just above and below) intersect with each other.<\/p>\n
    \n
    The step 2 is like passing a vertical line from all points starting from the leftmost point to the rightmost point. That is why this algorithm is called Sweep Line Algorithm. <\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t