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 =
- 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 axisint 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 Codeint 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 axisimport 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 axisstatic 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 Codepublic 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 axisusing 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 axisstatic 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 Codepublic 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 axisfunction 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 Codevar p = [ [ 1, 2 ], [ 1, 5 ], [ 1, 15 ], [ 2, 10 ] ];var n = p.length;// Function calldocument.write( NotParallel(p, n));// This code is contributed by itsok.</script> |
Output:
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/number-of-lines-from-given-n-points-not-parallel-to-x-or-y-axis/ […]