Click here to Skip to main content
15,867,686 members
Please Sign up or sign in to vote.
1.57/5 (4 votes)
See more:
Input: (1,1),(2,2),(3,3),(1,4)
output:(1,1),(2,2),(3,3)

Input:(1,1),(3,2),(5,3),(4,1),(2,3),(1,4)'
output:(1,4),(2,3),(3,2),(4,1)


//Below is code which is working for first case

What I have tried:

Python
def straightline(arr,n):
  x0 = arr[0][0]
  y0 = arr[0][1]

  x1 = arr[1][0]
  y1 =arr[1][1]

  dx = x1-x0
  dy = y1-y0

  for i in range(n):
   x = arr[i][0]
   y = arr[i][1]
   if (dx*(y-y1) != dy*(x-x1)):
     print(arr[i])
     return False
  print("Yes",end = "")
  return True

arr = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
n = len(arr)
straightline(arr,n)
Posted
Updated 19-Apr-22 8:14am
Comments
Ralf Meier 19-Apr-22 8:43am    
do you know the Specification of the Line you are searching for ?
Or the other way round : with your 1st sample you work with the line (1,1 - 2,2 - 3,3) - who says that this is the right line ? the right line could also be 1,1 - 1,4 and then the 2 points between are wrong ...?
the same with the 2nd line ...
Rohit kumar Gupta 2022 19-Apr-22 8:48am    
The inputs are the given points,you need to find max number of points from input points.
Like in second test case, there will be 2 straight line one with 4 coordinates given in the input and the other will be with 3 coordinates with one common coordinate(try to plot the coordinate for better understanding)
Ralf Meier 19-Apr-22 9:31am    
you have a kind of Line-definition : y= m*x + b
the only thing you need to do is to check how much of the point-pairs have the same Line-definition / matches to one line-definition ...
Rohit kumar Gupta 2022 19-Apr-22 8:50am    
Here's the exact question:
Given(x,y) cordinates on a 2d plane, find all the points that lie on the same straight line. Th epoints should be sorted from the starting point to the ending point.Note:No need to consider multiple points.
0x01AA 19-Apr-22 9:34am    
Your solution does also not work for the first example if you change the order of the points. The whole task is not that easy.
Btw. if you google for the text in your comment above you will find some help. E.g. Max Points On The Straight Line[^]

You can get some input here, it shows at least the logic, but not the final solution ;)

Max Points On The Straight Line[^]

[Edit]
A point not to be underestimated, which is not explained there, is to output the points sorted from start to finish. However you define start/finish...

I hope it helps a little bit.
 
Share this answer
 
v2
Comments
CPallini 20-Apr-22 2:05am    
5.
0x01AA 20-Apr-22 3:55am    
Thank you.
Quote:
I need to find the maximum number of points lieing on a single line.(IF possible dont use Python, c#recmommended)

First problem with your code : What tells you that the first 2 points in input are part of the strait line ?
As far as I can see, your code do not list the points on the line, and thus do not sort them.

Since the input can contain points with more than 1 line, there is only 1 algorithm :
- Supposing the input list do not contain the same point 2 time.
1- Choose a first point
2- Choose a second point
3- Check remaining point for being on same line
4- As you find a new point on same line, add it to a list of points
5- at the end of check, if new list is longer than previous list, remember for result
6- Take another second point and go back to 3
7- Take another first point and go back to 2
8- Sort longest list and return as result
 
Share this answer
 
Comments
0x01AA 19-Apr-22 14:21pm    
"Sort longest list and return as result": Sort how?

To be honest the whole task is not easy. It includes 'point on line', 'permutation', 'sort 2d' :-)

[Edit]
I forgot the numerical precision aspect ;)
CPallini 20-Apr-22 2:05am    
5.
Patrice T 20-Apr-22 2:10am    
Thank you.
While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

Just copy'n'pasting your homework question and expecting others to do the work for you isn't going to cut it ...

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900