savings

package tsp_ai;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class TSP_AI_SAVINGS {

    public static Place[] places;

    public static List<Tour> make_pair_tours(int start_pos, int total) {
        List<Tour> pairs = new ArrayList<Tour>();
        int j = 0;
        for (int i = 0; i < total; i++) {
            if (places[i].id != (start_pos + 1)) {
                Tour temp = new Tour();
                temp.pushback(places[start_pos]);
                temp.pushback(places[i]);
                temp.CalculateCost();
                pairs.add(temp);
            }
        }
//        System.out.println("In make pairs, sub_tours : " + pairs.size());
//        for (int i = 0; i < pairs.size(); i++) {
//            System.out.println(pairs.get(i));
//        }
        return pairs;
    }

    public static Tour Savings(int start_pos, int total) {
        List<Tour> sub_tours = make_pair_tours(start_pos, total);

        //Calculating savings
        int s = sub_tours.size();
        double[][] saving = new double[total][total];
        for (int i = 0; i < places.length; i++) {
            for (int j = 0; j < places.length; j++) {
                if (i != j) {
                    saving[i][j] = places[start_pos].dist(places[i]) + places[j].dist(places[start_pos]) - places[i].dist(places[j]);
                } else {
                    saving[i][j] = 0;
                }
            }
        }
        temp_ordering[] savings_in_order = new temp_ordering[total * total];
        int l = 0;
        // taking savings in 1-D Array
        for (int i = 0; i < places.length; i++) {
            for (int j = 0; j < places.length; j++) {
                savings_in_order[l] = new temp_ordering();
                savings_in_order[l].i = i;
                savings_in_order[l].j = j;
                savings_in_order[l].isUsed = false;
                savings_in_order[l].save = saving[i][j];
                l++;
            }
        }
        //Sorting 1-D Array of saving
        Arrays.sort(savings_in_order);

        //sorting test
//        for (int i = 0; i < savings_in_order.length; i++) {
//            System.out.println(savings_in_order[i]);
//        }
        // Merging Tours if merging is feasible
        for (int i = 0; i < savings_in_order.length; i+=2) {
            if ((savings_in_order[i].isUsed == false) && (savings_in_order[i].i != start_pos) && (savings_in_order[i].j != start_pos)) {
                int a = savings_in_order[i].i;
                int b = savings_in_order[i].j;
                Boolean feasible1 = false;
                Boolean feasible2 = false;
                Tour t1 = null;
                Tour t2 = null;
                int t1_idx_in_sub_tour, t2_idx_in_sub_tour;
                for (int j = 0; j < sub_tours.size(); j++) { // getting tours to be merged
                    if(sub_tours.get(j).t.contains(places[a])){
                        t1 = sub_tours.get(j);
                        t1_idx_in_sub_tour = j;
                    }
                    if(sub_tours.get(j).t.contains(places[b])){
                        t2 = sub_tours.get(j);
                        t2_idx_in_sub_tour = j;
                    }
                }
                if(t1 == t2){ // edge in same tour, so discard
                    continue;
                }

                int t1_size = t1.size();
                int t2_size = t2.size();
                int a_idx_in_t1 = t1.t.indexOf(places[a]);
                int b_idx_in_t2 = t2.t.indexOf(places[b]);
                if((a_idx_in_t1 == 1) || (a_idx_in_t1 == (t1_size - 1))){
                    feasible1 = true;
                }
                if((b_idx_in_t2 == 1) || (b_idx_in_t2 == (t2_size - 1))){
                    feasible2 = true;
                }
                if(feasible1 && feasible2){ // link breaking capability check
                    for (int j = 1; j < t2.size(); j++) {
                        t1.pushback(t2.t.get(j));
                    }
                    sub_tours.remove(t2);
                }
                if(sub_tours.get(0).size() == total && sub_tours.size() == 1){ // result has been constructed
                    break;
                }
            }
        }

        return sub_tours.get(0);
    }

    public static void main(String[] args) {
        Scanner in;
        in = new Scanner(System.in);
        int total;
        total = in.nextInt();
        places = new Place[total];
        for (int i = 0; i < total; i++) {
            int id = in.nextInt();
            double x = in.nextDouble();
            double y = in.nextDouble();
            Place temp = new Place(id, x, y);
            places[i] = temp;
        }
        Tour t = Savings(1, total); // start_pos in (placeid - 1) form
        System.out.println(t);
    }

}