# [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]);
}

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.