Menu
Question Index
...


Given the list of points, write a program to find the path of non intersecting polygon which goes through all those points. Non intersecting polygon is a polygon which does not intersect itself.
While returning the output, it is not necessary to exactly match the lines which are given in the requirements below. As long as they form a non intersecting polygon, it will be accepted.

Input (List of Points) Example Output (List of Lines)
[[3.0,3.0], [4.0,2.0], [1.0,1.0], [2.0,4.0], [5.0,5.0], [1.0,5.0], [2.0,7.0]] [[4.0,2.0]-[1.0,1.0], [1.0,1.0]-[1.0,5.0], [1.0,5.0]-[2.0,4.0], [2.0,4.0]-[3.0,3.0], [3.0,3.0]-[2.0,7.0], [2.0,7.0]-[5.0,5.0], [5.0,5.0]-[4.0,2.0]]
[[4.0,2.0], [1.0,1.0], [5.0,5.0], [1.0,5.0], [3.0,3.0], [2.0,7.0], [2.0,4.0]] [[4.0,2.0]-[1.0,1.0], [1.0,1.0]-[1.0,5.0], [1.0,5.0]-[2.0,7.0], [2.0,7.0]-[5.0,5.0], [5.0,5.0]-[2.0,4.0], [2.0,4.0]-[3.0,3.0], [3.0,3.0]-[4.0,2.0]]
[[2.0,2.0], [4.0,5.0], [3.0,1.0], [6.0,4.0]] [[2.0,2.0]-[4.0,5.0], [4.0,5.0]-[6.0,4.0], [6.0,4.0]-[3.0,1.0], [3.0,1.0]-[2.0,2.0]]
[[0.0,0.0], [3.0,0.0], [0.0,4.0]] [[0.0,0.0]-[3.0,0.0], [3.0,0.0]-[0.0,4.0], [0.0,4.0]-[0.0,0.0]]
[[2.0,2.0], [3.0,1.0], [5.0,1.0], [5.0,4.0]] [[2.0,2.0]-[3.0,1.0], [3.0,1.0]-[5.0,1.0], [5.0,1.0]-[5.0,4.0], [5.0,4.0]-[2.0,2.0]]
[[2.0,2.0], [3.0,4.0], [4.0,1.0], [8.0,5.0], [6.0,8.0]] [[2.0,2.0]-[3.0,4.0], [3.0,4.0]-[6.0,8.0], [6.0,8.0]-[8.0,5.0], [8.0,5.0]-[4.0,1.0], [4.0,1.0]-[2.0,2.0]]

class FindNonIntersectingPolygon

{    public static void main(String s[])
    {
        List points = new ArrayList();
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(1, 1));
        points.add(new Point(2, 4));
        points.add(new Point(5, 5));
        points.add(new Point(1, 5));
        points.add(new Point(2, 7));
        System.out.println("The path of the polygon : " + getPath(points));

    }


public static List<Line> getPath(List<Point> points) {
//Write code here to find the path of the non intersecting polygon
}

//If required, write any additional methods here
}
class Point {

double x;
double y;

Point(double x, double y) {
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj) {
return Math.abs(x - ((Point) obj).x) < 0.00001 && Math.abs(y - ((Point) obj).y) < 0.00001;
}

@Override
public String toString() {
return "[" + x + "," + y + "]";
}
}

class Line {

Point p1;
Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}

//If required write any additional methods here
@Override
public String toString() {
return p1.toString() + "-" + p2.toString();
}
}

Doubts

Problems

Topic: Collection Framework In Java

Read this topic
Take test on this topic

0
Wrong
Score more than 2 points

© meritcampus 2019

All Rights Reserved.

Open In App