Find the Intersections Points

Question

Find the Intersections
Given a set of N line segments, you need to find all the intersection points of all the horizontal line segments with all the vertical line segments. Don’t consider the coincident endpoints as intersections.
Input: First line consists of N denoting the number of line segments. Following N lines consist of xl,yl,x2,y2 each where (xl, yl) represents the starting point of line segment and (x2, y2) represents the ending point of line segment. The line segments would either be horizontal or vertical.
Output: Print all the intersection points as asked in the question in a separate line in sorted order. The intersection point is represented as (x,y) with space between them.See the sample output for clarity.
Constraints: 1 < N < 103 For horizontal line: 1 < xl < x2 < 106 1 < yl = y2 < 106 For vertical line: 1 < xl = x2 < 106 1 < yl < y2 < 106
SAMPLE INPUT
3 1 2 4 2 2 1 2 3 3 1 3 3
SAMPLE OUTPUT
2 2
3 2

Summary

Here we have given a set of N line segments. And we need to find the intersection points of all the horizontal line segments with all the vertical line segments. We also have a sample input and output.

Explanation

First, we include the header files. After that, there is the main method. In that main method we declare a variable n with a data type int. So next we add the cin function. next, we have to store vertices of the horizontal and vertical lines separately. Next, we add the for loop so that we can have each line numbers. So we also add if and else if condition. So that user can add the number in horizontal and vertical order as he wants. And after this there is a nested for loop to check if there is a intersection or not. once all this is done we have our output on the screen.

Code

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    /* to store the vertices of the horizontal and vertical lines separately */
    int h[n][4],v[n][4];
    int cc1=0,cc2=0;
    /* to have each line */
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        /* if teh line is horizontal */
        if(y1==y2){
            h[cc1][0]=x1;h[cc1][1]=y1;h[cc1][2]=x2;h[cc1][3]=y2;
            cc1++;
        }
        /* if the line is vertical */
        else if(x1==x2){
            v[cc2][0]=x1;v[cc2][1]=y1;v[cc2][2]=x2;v[cc2][3]=y2;
            cc2++;
        }
    }
    cout<<endl;
    /* for every horizontal line and vertical line pair, 
    checking if there is an intersection */
    for(int i=0;i<cc1;i++){
        for(int j=0;j<cc2;j++){
        if(h[i][0]<=v[j][0] && h[i][2]>=v[j][0] && v[j][1]<=h[i][1] && v[j][3]>=h[i][1])
        cout<<v[j][0]<<" "<<h[i][1]<<endl;
        }
    }
}

Output

Also read, Listing entity types and relationship types