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

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

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.

- Line formed by connecting any two-points will be parallel to
- 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 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:**

3

**Time Complexity:** O(N)

**Auxiliary Space: **O(N)