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

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.

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);
}
}
```

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

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.

Recommended Posts