Find the K closest points to the origin in 2D plane, given an array containing N

Question

Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multi, and division).

You may use collections/containers found in the JDK or the standard template library. Your solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following:

Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multi, and division). You may use collections/containers found in the JDK or the standard template library. Your solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following: Document your assumptions Explain your approach and how you intend to solve the problem Provide code comments where applicable Explain the big-O run time complexity of your solution. Justify your answer. Identify any additional data structures you used and justify why you used them. Only provide your best answer to the question.

Explanation / Answer

import java.awt.Point;

import sun.misc.Sort;

public class Closest

{

public static void main(String args[])

{

Point p1=new Point(2, 3);

Point p2=new Point(1, 2);

Point p3=new Point(1, 4);

Point p4=new Point(2, 4);

Point[] p={p1,p2,p3,p4};

Closest c1=new Closest();

Double d1=c1.distance(p1);

Double d2=c1.distance(p2);

Double d3=c1.distance(p3);

Double d4=c1.distance(p4);

Double val[]={d1,d2,d3,d4};

Double close =c1.bubbleSortInAscendingOrder(val)[0];

for(int i=0;i<val.length;i++)

{

if(close==val[i])

{

System.out.println("closest point is :(+"+p[i].getX()+","+p[i].getY()+")");

}

}

System.out.println("distance of closet point from origin is:"+c1.bubbleSortInAscendingOrder(val)[0]);

}

public Double distance(Point x)

{

Double d=Math.sqrt((x.getX())*(x.getX()) +(x.getY())*(x.getY()));

return d;

}

public Double[] bubbleSortInAscendingOrder( Double numbers[])

{

Double temp;

for(int i = 0; i < numbers.length; i++)

{

for(int j = 1; j < (numbers.length -i); j++)

{

  

if(numbers[j-1] > numbers[j])

{

temp = numbers[j-1];

numbers[j-1]=numbers[j];

numbers[j]=temp;

}

}

}

return numbers;

}

  

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.