[JAVA] I tried to solve the paiza campaign problem "Challenge from Kaito 813"

After solving the problem, I heard that I could get an Amazon gift certificate or meat by lottery, so I tried it. https://paiza.jp/poh/phantom_thief

problem

The treasure location information is written with the x, y coordinates of N treasures in meters, with the location of the phantom thief as 0, 0. It moves in a straight line between each coordinate. Start from the 0,0 position and output the route that steals all the treasure with the shortest possible route.

Way of thinking

If you output the coordinates closest to the origin, output the coordinates closest to that coordinate again, and so on, you can proceed with a short route. I thought, I tried to solve it.

It was written that the answer could be written on a blog, so I posted it below.

Submission code

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine().replaceAll(" ","");
        int itemCount = Integer.parseInt(firstLine);
        
        ArrayList<Point> pointList = new ArrayList<Point>();
        
        //Create a coordinate list from standard input
        for(int i = 0; i < itemCount ; i++){
            String[] line = sc.nextLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            pointList.add(new Point(x,y));
        }
        
        Point originPoint = new Point(0,0);
        while(pointList.size() > 0){
            int minDistance = Integer.MAX_VALUE;
            Point minDistancePoint = new Point();

            //Get the coordinates closest to the reference point from the coordinate list
            for(Point getPoint : pointList){
                int tmpDistance = getDistance(originPoint,getPoint);
                if(minDistance > tmpDistance){
                    minDistance = tmpDistance;
                    minDistancePoint = getPoint;
                }
            }
            //Display coordinate position
            minDistancePoint.output();
            //Change the reference point
            originPoint = minDistancePoint;
            //Remove coordinates from the coordinate list
            int index = pointList.indexOf(minDistancePoint);
            pointList.remove(index);
        }
    }

    //Find the distance between the coordinates of two points
    public static int getDistance(Point p1, Point p2) {
            double x1 = p1.x;
            double y1 = p1.y;
            double x2 = p2.x;
            double y2 = p2.y;

        double distance = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        return (int) distance;
    }

}

//Coordinate class
class Point{
    int x;
    int y;
    
    public Point(){
        this.x = 0;
        this.y = 0;
    }
    
    public Point(int x , int y){
        this.x = x;
        this.y = y;
    }
        
    public void output(){
        System.out.println(x + " " + y);
    }
}

result

Here. It seems that it was not the optimal solution. https://paiza.jp/poh/phantom_thief/result/a8a222d8

How to find the optimal solution?

After a little research, [Traveling Salesman Problem](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3 It seems to be a problem called% 83% AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F% E9% A1% 8C). (Is it a little different because you don't have to go back to the first coordinates?)

The method I solved this time seems to be an algorithm called "greedy method".

Algorithms for solving the traveling salesman problem include the "2-opt method", "hill climbing method", and "simulated annealing method". Using these methods seems to be closer to the optimal solution, but I gave up because it seems difficult.