Maximum number of distinct straight lines through a point in C

We get the number N for each line and the coordinates of the two points (x1,y1) and (x2,y2). The goal is to find the maximum number of straight lines from the given straight lines that can pass through a single point such that no two straight lines cover each other and no rotation is performed.

We will represent the straight line as (pair) m,c) where y=mx c,m is the slope m=y2-y1/x2-x1

Given c1!=c2, Lines with the same m are parallel. We will calculate different slopes in meters. For a vertical line, if x1=x2, then slope = INT_MAX, otherwise m.

Let us understand through examples.

Input

Line 1 (x1,y1)=(4,10) (x2,y2)=(2,2)
Line 2 (x1,y1)=(2,2) (x2,y2)=(1,1)

Output

Maximum lines: 2

Explanation - The number of bus lines is 2. The slopes of the two lines are different.

Input

Line 1 (x1,y1)=(1,5) (x2,y2)=(3,2)
Line 2 (x1,y1)=(2,7) (x2,y2)=(2,8)

Output

Maximum lines: 2

Explanation - The number of bus lines is 2. Both have different slopes.

The methods used in the following program are as follows

• The integer arrays x1[] and x2[] are used to store the coordinates of points on the line.

• Function numLines(int x1[],int y1[], int x2[], int y2[]) is counting the number of lines passing through a single point.

• Apply the formula to each point in x1[],y1[],x2[],y2[] to calculate the slope and use k to increment the slope count.

• Array s[] stores slope values.

  >

• Return k as the number of rows in the result.

Example

Live Demonstration

#include <stdio.h>
int numLines(int n, int x1[], int y1[], int x2[], int y2[]){
   double s[10];
   int k=0;
   double slope;
   for (int i = 0; i < n; ++i) {
      if (x1[i] == x2[i])
         slope = 999;
      else
         slope = (y2[i] - y1[i]) * 1.0 / (x2[i] - x1[i]) * 1.0;
         s[k++]=slope;
   }
   return k;
}
int main(){
   int n = 2;
   int x1[] = { 1, 5 }, y1[] = { 3, 2 };
   int x2[] = { 2,7 }, y2[] = { 2, 8 };
   printf("Maximum lines: %d", numLines(n, x1, y1, x2, y2));
   return 0;
}

Output

If we run the above code, it will generate the following output-

Maximum distinct lines passing through a single point : 2

The above is the detailed content of Maximum number of distinct straight lines through a point in C. For more information, please follow other related articles on the PHP Chinese website!