Points Collision

Last Updated on March 31, 2022 by Ria Pathak

CONCEPTS USED:

Computational geometry.

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

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
(Xi,Yi) and (Xj,Yj) (1<=i,j<=n). Coordinates of these points are integer numbers with real value smaller than 1000
. Length of each segment is positive.
When 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.

See original problem statement here

For Example :

Input
3
3
0 0 2 0
1 -1 1 1
2 2 3 3
2
0 0 1 1
1 0 0 1
2
0 0 0 1
0 2 0 3

Output
1
0
2

BRUTE FORCE:

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).

Sweep Line Algorithm:

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.

1. 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.

2. Start from the leftmost point. Do following for every point

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.

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.

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.

SOLUTIONS:

#include <stdio.h>
#include<stdlib.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
struct Point {
    double x, y;
};
struct Segment {
    Point s, t;
};
double in(double a, double b, double c) {
    return c >= a && c <= b;
}
int onLine(Segment a, Point c) {
    static double minx, maxx, miny, maxy;
    minx = min(a.s.x, a.t.x);
    maxx = max(a.s.x, a.t.x);
    miny = min(a.s.y, a.t.y);
    maxy = max(a.s.y, a.t.y);
    if(in(minx, maxx, c.x) != 0 && in(miny, maxy, c.y) != 0) {
        if((a.s.x-a.t.x)*(c.y-a.s.y) == (a.s.y-a.t.y)*(c.x-a.s.x)) {
            return 1;
        }
    }
    return 0;
}
double cross(Point &o, Point &a, Point &b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int intersection(Segment a, Segment b) {
    if(onLine(a, b.s) || onLine(a, b.t) || onLine(b, a.s) || onLine(b, a.t))
        return 1;
    if(cross(a.s, a.t, b.s)*cross(a.s, a.t, b.t) < 0 &&
       cross(a.t, a.s, b.s)*cross(a.t, a.s, b.t) < 0 &&
       cross(b.s, b.t, a.s)*cross(b.s, b.t, a.t) < 0 &&
       cross(b.t, b.s, a.s)*cross(b.t, b.s, a.t) < 0
       )
        return 1;
    return 0;
}
int main() {
    int t, n, i, j;
    Segment line[1000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%lf %lf %lf %lf", &line[i].s.x, &line[i].s.y, &line[i].t.x, &line[i].t.y);
        int ans = 0;
        for(i = 0; i < n; i++) {
            int flag = 0;
            for(j = 0; j < n; j++) {
                if(i == j)
                    continue;
                if(intersection(line[i], line[j])) {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
struct Point {
    double x, y;
};
struct Segment {
    Point s, t;
};
double in(double a, double b, double c) {
    return c >= a && c <= b;
}
int onLine(Segment a, Point c) {
    static double minx, maxx, miny, maxy;
    minx = min(a.s.x, a.t.x);
    maxx = max(a.s.x, a.t.x);
    miny = min(a.s.y, a.t.y);
    maxy = max(a.s.y, a.t.y);
    if(in(minx, maxx, c.x) != 0 && in(miny, maxy, c.y) != 0) {
        if((a.s.x-a.t.x)*(c.y-a.s.y) == (a.s.y-a.t.y)*(c.x-a.s.x)) {
            return 1;
        }
    }
    return 0;
}
double cross(Point &o, Point &a, Point &b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int intersection(Segment a, Segment b) {
    if(onLine(a, b.s) || onLine(a, b.t) || onLine(b, a.s) || onLine(b, a.t))
        return 1;
    if(cross(a.s, a.t, b.s)*cross(a.s, a.t, b.t) < 0 &&
       cross(a.t, a.s, b.s)*cross(a.t, a.s, b.t) < 0 &&
       cross(b.s, b.t, a.s)*cross(b.s, b.t, a.t) < 0 &&
       cross(b.t, b.s, a.s)*cross(b.t, b.s, a.t) < 0
       )
        return 1;
    return 0;
}
int main() {
    int t, n, i, j;
    Segment line[1000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%lf %lf %lf %lf", &line[i].s.x, &line[i].s.y, &line[i].t.x, &line[i].t.y);
        int ans = 0;
        for(i = 0; i < n; i++) {
            int flag = 0;
            for(j = 0; j < n; j++) {
                if(i == j)
                    continue;
                if(intersection(line[i], line[j])) {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

This article tried to discuss the concept of Computational Geometry.Hope this blog helps you solve the problem based on Computational Geometry.To practice more problems you can check out MYCODE | Competitive Programming.