// Project Identifier: 9B734EC0C043C5A836EA0EBE4BEFEA164490B2C7
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <limits>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <getopt.h>
#include <algorithm>
#include <unordered_map>
#include "MST.h"


////////////
//INPUT
//utilities
bool is_land(Pokemon &pokemon){
    if(pokemon.x > 0 && pokemon.y > 0){
        return true;
    }
    return false;
}

bool is_coast(Pokemon &pokemon){
     if(pokemon.x <= 0 && pokemon.y == 0){
        return true;
    }
    else if(pokemon.x == 0 && pokemon.y <= 0){
        return true;
    }
    return false;
}
    
bool is_sea(Pokemon &pokemon){
     if(pokemon.x < 0 && pokemon.y < 0){
        return true;
    }
    return false;  
}

//get pokemon
void get_pokemon(vector<Pokemon> &container){
    //get pokemon num
    size_t num;
    cin >> num;
    //for pokemon num, cin pokemon and add to vector
    for(size_t i=0; i < num; i++){
        int x, y;
        cin >> x >> y;
        Pokemon new_pokemon = Pokemon(i, x, y);
        if(is_sea(new_pokemon)){
            new_pokemon.is_sea = true;
        }
        else if(is_coast(new_pokemon)){
            new_pokemon.is_coast = true;
        }
        else{
            new_pokemon.is_land = true;
        }
        container.push_back(new_pokemon);
    }
}

//euclidean distance
double find_the_distance(double &ax, double &ay, double &bx, double &by){
    return sqrt((double)pow((bx - ax), 2) + pow((by - ay), 2));
}

//returns weight from two pokemon
double find_the_weight(Pokemon &pokemon_a, Pokemon &pokemon_b){
    return find_the_distance(pokemon_a.x, pokemon_a.y, pokemon_b.x, pokemon_b.y);
}

//PART A
void check_the_mst(vector<Pokemon> &container){
    int land_num = 0;
    int sea_num = 0;
    int coast_num = 0;
    for(size_t i=0; i< container.size(); i++){
        if(container[i].x > 0 && container[i].y > 0){
            land_num++;
        }
        else if(container[i].x < 0 && container[i].y < 0){
            sea_num++;
        }
        else if(container[i].x == 0 && container[i].y <= 0){
            coast_num++;
        }
        else if(container[i].x <= 0 && container[i].y == 0){
            coast_num++;
        }
    }
    if(land_num > 0 && sea_num > 0 && coast_num < 1){
        cerr << "Cannot construct MST tree\n";
        exit(1);
    }
}

//run mst
void run_the_mst(vector<Pokemon> &container){
    //initialize
    double total_weight = 0;
    size_t min_index = 0;
	size_t edge_index = 0;
    size_t i = 0;

    //set begin
    container[0].distance = 0;
	container[0].prev = 0;

    //start loop
    while(i < container.size() - 1){
        double weight = 0;
        //initialize min
        double min_weight = numeric_limits<double>::infinity();
        
        //set min index
        min_index = edge_index;
        container[min_index].visited = true;

        //add distance
        total_weight += container[min_index].distance;
		
        //if pokemon at min edge index is land
        if(container[min_index].is_land){
            //find edge end
			for(size_t j = 0; j < container.size(); j++){
                if(!container[j].visited){
                    //if edge end is land/coast
					if(container[j].is_land|| container[j].is_coast){
						weight = find_the_weight(container[min_index], container[j]);
                        //if distance is min, create edge
						if(weight < container[j].distance){
                            container[j].prev = min_index;
							container[j].distance = weight;
						}
					}
                    //if distance of edge end is less than min_weight
                    if(container[j].distance - min_weight < 0){
					    min_weight = container[j].distance;
					    edge_index = j;
                    }
				}
			}
		}
        //if pokemon at min edge index is sea
		else if(container[min_index].is_sea){
			for(size_t j = 0; j < container.size(); j++) {
                if(!container[j].visited){
                    //if edge end is sea/coast
					if(container[j].is_sea || container[j].is_coast){
						weight = find_the_weight(container[min_index], container[j]);
						if(weight < container[j].distance){
                            container[j].prev = min_index;
							container[j].distance = weight; 
						}
                    }
                    if(container[j].distance - min_weight < 0){
					    min_weight = container[j].distance;
                        edge_index = j;
                    }
				}
            }
		}
        //if pokemon at min edge index is coast
		else {
			for(size_t j = 0; j < container.size(); j++){
				if(!container[j].visited){
					weight = find_the_weight(container[min_index], container[j]);
					if(weight < container[j].distance){
                        container[j].prev = min_index;
						container[j].distance = weight;
					}
                    if(container[j].distance - min_weight < 0){
                        min_weight= container[j].distance;
                        edge_index = j;
                    }
				}
			}
		}
    i++;
    }
    //add last edge
    min_index = edge_index;
    total_weight += container[min_index].distance;
    //output
	cout << total_weight << "\n";
    for(size_t i = 1; i < container.size(); i++) {
		cout << min(container[i].id, container[i].prev) << " " << max(container[i].id, container[i].prev) << "\n";
    }
}












////////////

// UTILITIES //////////////////////////////////////////////////////////////////////////////
// euclidean distance
double find_distance(double &ax, double &ay, double &bx, double &by){
    return sqrt((double)pow((bx - ax), 2) + pow((by - ay), 2));
}

// returns weight from two locations
double find_weight(Location &location_a, Location &location_b){
    return find_distance(location_a.x, location_a.y, location_b.x, location_b.y);
}

// INPUT //////////////////////////////////////////////////////////////////////////////////
// process command line
void process_cmd_line(int argc, char** argv, Line_args &line_args){
    std::string spec = "";
    //getopt
    int gotopt;
    int option_index = 0;
    
    static struct option long_opts[] = {
        {"help", no_argument, nullptr, 'h'},
        {"mode", required_argument, nullptr, 'm'},
        {NULL, 0, NULL, 0}
    };
    while((gotopt = getopt_long(argc, argv, "hm:", 
            long_opts, &option_index)) != -1){
        switch(gotopt){
            case 'h':
                print_help();
                exit(0);

            case 'm':
                spec = optarg;
                if(spec == "MST"){
                    line_args.is_mst = true;
                }
                else if(spec == "FASTTSP"){
                    line_args.is_fasttsp = true;
                }
                else if(spec == "OPTTSP"){
                    line_args.is_opttsp = true;
                }
                else if(spec == ""){
                    std::cerr << "Error: No mode specified\n";
                    exit(1);
                }
                else {
                    std::cerr << "Error: Invalid mode\n";
                    exit(1);
                }
                break;
            default:
                std::cerr << "Error: Invalid command line option\n";
                exit(1);
            abort();
        }
    }
}

// get locations
void get_locations(std::vector<Location> &container){
    size_t num = 0;
    std::cin >> num;
    // for num locations, cin location and add to vector
    for(size_t i=0; i < num; i++){
        int x, y;
        std:: cin >> x >> y;
        Location new_location = Location(i, x, y);
        container.push_back(new_location);
    }
}

//print help
void print_help(){
    std::cout << "This program takes a mode parameter in the form of MST, FASTTSP, OPTTSP\n";
}

// FUNCTIONS //////////////////////////////////////////////////////////////////////////////
// PART A
// check mst
// MST cannot be constructed if there are locations in lab and outer, but none in DC
void check_mst(std::vector<Location> &container){
    int lab_num = 0;
    int dc_num = 0;
    int outer_num = 0;
    for(size_t i=0; i < container.size(); i++){
        if(container[i].is_lab()){
            lab_num++;
        }
        else if(container[i].is_dc()){
            dc_num++;
        }
        else if(container[i].is_outer()){
            outer_num++;
        }
    }
    if(lab_num > 0 && outer_num > 0 && dc_num < 1){
        std::cerr << "Cannot construct MST tree\n";
        exit(1);
    }
}

// run mst
void run_mst(std::vector<Location> &container){
    // initialize
    double total_weight = 0;
    size_t min_index = 0;
    size_t edge_index = 0;
    size_t i = 0;
    
    // set beginning
    container[0].distance = 0;
    container[0].prev = 0;

    // start loop
    while(i < container.size() - 1){
        // initialize weight values
        double weight = 0;
        double min_weight = std::numeric_limits<double>::infinity();
        
        // set min index
        min_index = edge_index;
        container[min_index].visited = true;

        // add distance
        total_weight += container[min_index].distance;

        // if location at min edge index is in 
        if(container[min_index].is_outer()){
            // find edge end
            for(size_t j=0; j < container.size(); j++){
                if(!container[j].visited){
                    // if edge end is outer/dc
                    if(container[j].is_outer() || container[j].is_dc()){
                        weight = find_weight(container[min_index], container[j]);
                        // if distance is min, create edge
                        if(weight < container[j].distance){
                            container[j].prev = min_index;
                            container[j].distance = weight;
                        }
                    }
                    // if distance of edge end is less than min_weight
                    if(container[j].distance - min_weight < 0){
                        min_weight = container[j].distance;
                        edge_index = j;
                    }
                }
            }
        }
        // if location at min_index is lab
        else if(container[min_index].is_lab()){
            for(size_t j=0; j < container.size(); j++){
                if(!container[j].visited){
                    // if edge end is lab/dc
                    if(container[j].is_lab() || container[j].is_dc()){
                        weight = find_weight(container[min_index], container[j]);
                        if(weight < container[j].distance){
                            container[j].prev = min_index;
                            container[j].distance = weight;
                        }
                    }
                    if(container[j].distance - min_weight < 0){
                        min_weight = container[j].distance;
                        edge_index = j;
                    }
                }
            }
        }
        // if location at min_index is dc
        else{
            for(size_t j=0; j < container.size(); j++){
                if(!container[j].visited){
                    weight = find_weight(container[min_index], container[j]);
                    if(weight < container[j].distance){
                        container[j].prev = min_index;
                        container[j].distance = weight;
                    }
                    if(container[j].distance - min_weight < 0){
                        min_weight = container[j].distance;
                        edge_index = j;
                    }
                }
            }
        }
        i++;
    }
    // add last edge
    min_index = edge_index;
    total_weight += container[min_index].distance;
    // output
    std::cout << total_weight << "\n";
    for(size_t i=1; i < container.size(); i++){
        std::cout << std::min(container[i].id, container[i].prev) << " " << std::max(container[i].id, container[i].prev) << "\n";
    }
}