Number of lines from given N points not parallel to X or Y axis

0 0 7 minutes read

Given N distinct integers points on 2D Plane. The task is to count the number of lines which are formed from given N points and not parallel to X or Y-axis.

Examples:

Input: points[][] = {{1, 2}, {1, 5}, {1, 15}, {2, 10}}
Output: 3
Chosen pairs are {(1, 2), (2, 10)}, {(1, 5), (2, 10)}, {(1, 15), (2, 10)}.

Input: points[][] = {{1, 2}, {2, 5}, {3, 15}}
Output: 3
Choose any pair of points.

Approach:

We know that
- Line formed by connecting any two-points will be parallel to X-axis if they have the same Y coordinates
- It will be parallel to Y-axis if they have the same X coordinates.
Total number of line segments that can formed from N points = $\binom{N}{2}= \frac{N*(N-1)}{2}$
Now we will exclude those line segments which are parallel to the X-axis or the Y-axis.
For each X coordinate and Y coordinate, calculate the number of points and exclude those line segments at the end.

Below is the implementation of above approach:

C++

// C++ program to find the number
// of lines which are formed from
// given N points and not parallel
// to X or Y axis
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of lines
// which are formed from given N points
// and not parallel to X or Y axis
int NotParallel(int p[][2], int n)
{
    // This will store the number of points has
    // same x or y coordinates using the map as
    // the value of coordinate can be very large
    map<int, int> x_axis, y_axis;
 
    for (int i = 0; i < n; i++) {
 
        // Counting frequency of each x and y
        // coordinates
        x_axis[p[i][0]]++;
        y_axis[p[i][1]]++;
    }
 
    // Total number of pairs can be formed
    int total = (n * (n - 1)) / 2;
 
    for (auto i : x_axis) {
        int c = i.second;
 
        // We can not choose pairs from these as
        // they have same x coordinatethus they
        // will result line segment
        // parallel to y axis
        total -= (c * (c - 1)) / 2;
    }
 
    for (auto i : y_axis) {
        int c = i.second;
 
        // we can not choose pairs from these as
        // they have same y coordinate thus they
        // will result line segment
        // parallel to x-axis
        total -= (c * (c - 1)) / 2;
    }
 
    // Return the required answer
    return total;
}
 
// Driver Code
int main()
{
 
    int p[][2] = { { 1, 2 },
                   { 1, 5 },
                   { 1, 15 },
                   { 2, 10 } };
 
    int n = sizeof(p) / sizeof(p[0]);
 
    // Function call
    cout << NotParallel(p, n);
 
    return 0;
}

Java

// Java program to find the number
// of lines which are formed from
// given N points and not parallel
// to X or Y axis
import java.util.*;
 
class GFG{
  
// Function to find the number of lines
// which are formed from given N points
// and not parallel to X or Y axis
static int NotParallel(int p[][], int n)
{
    // This will store the number of points has
    // same x or y coordinates using the map as
    // the value of coordinate can be very large
    HashMap<Integer,Integer> x_axis = new HashMap<Integer,Integer>();
    HashMap<Integer,Integer> y_axis = new HashMap<Integer,Integer>();
  
    for (int i = 0; i < n; i++) {
  
        // Counting frequency of each x and y
        // coordinates
        if(x_axis.containsKey(p[i][0]))
            x_axis.put(p[i][0], x_axis.get(p[i][0])+1);
        else
            x_axis.put(p[i][0], 1);
        if(y_axis.containsKey(p[i][1]))
            y_axis.put(p[i][1], y_axis.get(p[i][1])+1);
        else
            y_axis.put(p[i][1], 1);
    }
  
    // Total number of pairs can be formed
    int total = (n * (n - 1)) / 2;
  
    for (Map.Entry<Integer,Integer> i : x_axis.entrySet()) {
        int c = i.getValue();
  
        // We can not choose pairs from these as
        // they have same x coordinatethus they
        // will result line segment
        // parallel to y axis
        total -= (c * (c - 1)) / 2;
    }
  
    for (Map.Entry<Integer,Integer> i : y_axis.entrySet()) {
        int c = i.getValue();
  
        // we can not choose pairs from these as
        // they have same y coordinate thus they
        // will result line segment
        // parallel to x-axis
        total -= (c * (c - 1)) / 2;
    }
  
    // Return the required answer
    return total;
}
  
// Driver Code
public static void main(String[] args)
{
  
    int p[][] = { { 1, 2 },
                   { 1, 5 },
                   { 1, 15 },
                   { 2, 10 } };
  
    int n = p.length;
  
    // Function call
    System.out.print(NotParallel(p, n));
  
}
}
 
// This code is contributed by PrinciRaj1992

C#

// C# program to find the number
// of lines which are formed from
// given N points and not parallel
// to X or Y axis
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to find the number of lines
// which are formed from given N points
// and not parallel to X or Y axis
static int NotParallel(int [,]p, int n)
{
    // This will store the number of points has
    // same x or y coordinates using the map as
    // the value of coordinate can be very large
    Dictionary<int,int> x_axis = new Dictionary<int,int>();
    Dictionary<int,int> y_axis = new Dictionary<int,int>();
   
    for (int i = 0; i < n; i++) {
   
        // Counting frequency of each x and y
        // coordinates
        if(x_axis.ContainsKey(p[i, 0]))
            x_axis[p[i, 0]] = x_axis[p[i, 0]] + 1;
        else
            x_axis.Add(p[i, 0], 1);
        if(y_axis.ContainsKey(p[i, 1]))
            y_axis[p[i, 1]] = y_axis[p[i, 1]] + 1;
        else
            y_axis.Add(p[i, 1], 1);
    }
   
    // Total number of pairs can be formed
    int total = (n * (n - 1)) / 2;
   
    foreach (KeyValuePair<int,int> i in x_axis) {
        int c = i.Value;
   
        // We can not choose pairs from these as
        // they have same x coordinatethus they
        // will result line segment
        // parallel to y axis
        total -= (c * (c - 1)) / 2;
    }
   
    foreach (KeyValuePair<int,int> i in y_axis) {
        int c = i.Value;
   
        // we can not choose pairs from these as
        // they have same y coordinate thus they
        // will result line segment
        // parallel to x-axis
        total -= (c * (c - 1)) / 2;
    }
   
    // Return the required answer
    return total;
}
   
// Driver Code
public static void Main(String[] args)
{
   
    int [,]p = { { 1, 2 },
                   { 1, 5 },
                   { 1, 15 },
                   { 2, 10 } };
   
    int n = p.GetLength(0);
   
    // Function call
    Console.Write(NotParallel(p, n));  
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to find the number 
# of lines which are formed from 
# given N points and not parallel 
# to X or Y axis 
 
# Function to find the number of lines 
# which are formed from given N points 
# and not parallel to X or Y axis 
def NotParallel(p, n) : 
 
    # This will store the number of points has 
    # same x or y coordinates using the map as 
    # the value of coordinate can be very large 
    x_axis  = {}; y_axis = {}; 
 
    for i in range(n) :
 
        # Counting frequency of each x and y 
        # coordinates 
        if p[i][0] not in x_axis :
            x_axis[p[i][0]] = 0;
             
        x_axis[p[i][0]] += 1; 
 
        if p[i][1] not in y_axis :
            y_axis[p[i][1]] = 0;
         
        y_axis[p[i][1]] += 1; 
 
    # Total number of pairs can be formed 
    total = (n * (n - 1)) // 2; 
 
    for i in x_axis :
        c =  x_axis[i]; 
 
        # We can not choose pairs from these as 
        # they have same x coordinatethus they 
        # will result line segment 
        # parallel to y axis 
        total -= (c * (c - 1)) // 2; 
 
    for i in y_axis : 
        c = y_axis[i]; 
 
        # we can not choose pairs from these as 
        # they have same y coordinate thus they 
        # will result line segment 
        # parallel to x-axis 
        total -= (c * (c - 1)) // 2; 
     
    # Return the required answer 
    return total; 
 
 
# Driver Code 
if __name__ == "__main__" : 
 
    p = [ [ 1, 2 ], 
            [1, 5 ], 
            [1, 15 ], 
            [ 2, 10 ] ]; 
 
    n = len(p); 
 
    # Function call 
    print(NotParallel(p, n)); 
 
    # This code is contributed by AnkitRai01 

Javascript

<script>
 
// Javascript program to find the number
// of lines which are formed from
// given N points and not parallel
// to X or Y axis
 
// Function to find the number of lines
// which are formed from given N points
// and not parallel to X or Y axis
function NotParallel(p, n)
{
    // This will store the number of points has
    // same x or y coordinates using the map as
    // the value of coordinate can be very large
    var x_axis = new Map(), y_axis = new Map();
 
    for (var i = 0; i < n; i++) {
 
        // Counting frequency of each x and y
        // coordinates
        if(x_axis.has(p[i][0]))
            x_axis.set(p[i][0], x_axis.get(p[i][0])+1)
        else
            x_axis.set(p[i][0], 1)
         
        if(y_axis.has(p[i][1]))
            y_axis.set(p[i][1], y_axis.get(p[i][1])+1)
        else
            y_axis.set(p[i][1], 1)
    }
 
    // Total number of pairs can be formed
    var total = (n * (n - 1)) / 2;
 
    x_axis.forEach((value, key) => {
         
        var c = value;
 
        // We can not choose pairs from these as
        // they have same x coordinatethus they
        // will result line segment
        // parallel to y axis
        total -= (c * (c - 1)) / 2;
    });
 
    y_axis.forEach((value, key) => {
         
        var c = value;
 
        // we can not choose pairs from these as
        // they have same y coordinate thus they
        // will result line segment
        // parallel to x-axis
        total -= (c * (c - 1)) / 2;
    });
 
    // Return the required answer
    return total;
}
 
// Driver Code
var p = [ [ 1, 2 ],
               [ 1, 5 ],
               [ 1, 15 ],
               [ 2, 10 ] ];
var n = p.length;
 
// Function call
document.write( NotParallel(p, n));
 
// This code is contributed by itsok.
</script>

Output:

Time Complexity: O(N)

Auxiliary Space: O(N), since N extra space has been taken.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!