// 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>

using namespace std;

// STRUCTURES /////////////////////////////////////////////////////////////////////////////
// line args
struct Line_args {
    bool is_mst;
    bool is_fasttsp;
    bool is_opttsp;
    Line_args(): is_mst(false), is_fasttsp(false), is_opttsp(false){}
};

//pokemon
class Pokemon{
    public:
    size_t id;
    double x;
    double y;
    double distance;
    size_t prev;
    bool is_land;
    bool is_coast;
    bool is_sea;
    bool visited;
    Pokemon(size_t &id_num, int &x_coord, int &y_coord): id(id_num), x(x_coord), y(y_coord), distance(numeric_limits<double>::infinity()), prev(0), is_land(false), is_coast(false), is_sea(false), visited(false){}
};

// location
class Location{
    public:
    size_t id;
    size_t prev;
    double x;
    double y;
    double distance;
    int visited; // visited = 1, not visited = 0
    
    // retrive location terrain
    bool is_lab();
    bool is_outer();
    bool is_dc();
    
    Location(size_t &id_num, int &x_coord, int &y_coord): id(id_num), prev(0), x(x_coord), y(y_coord), distance(std::numeric_limits<double>::infinity()), visited(0){}
};

// return if location is in outer area (Else)
inline bool Location::is_outer(){
    if(x > 0 && y > 0){
        return true;
    }
    return false;
}

// return if location is in decontamination zone (Q3 Boundary)
inline bool Location::is_dc(){
    if(x <= 0 && y == 0){
        return true;
    }
    else if(x == 0 && y <= 0){
        return true;
    }
    return false;
}
// return if location is in lab (Q3)
inline bool Location::is_lab(){
    if(x < 0 && y < 0){
        return true;
    }
    return false;  
}




////////////////////////////////////////////////////////////////////////////////////////////////////////////
//utilities
bool is_land(Pokemon &pokemon);
bool is_coast(Pokemon &pokemon);
bool is_sea(Pokemon &pokemon);

//gets pokemon
void get_pokemon(vector<Pokemon> &container);
//process input
void process_input();

//euclidean distance
double find_the_distance(double &ax, double &ay, double &bx, double &by);

//returns weight from two pokemon
double find_the_weight(Pokemon &pokemon_a, Pokemon &pokemon_b);
    

//PART A ------------------------
//check mst
void check_the_mst(vector<Pokemon> &container);
//run mst
void run_the_mst(vector<Pokemon> &container);



// UTILITIES //////////////////////////////////////////////////////////////////////////////
// euclidean distance
double find_distance(double &ax, double &ay, double &bx, double &by);

// returns weight from two locations
double find_weight(Location &location_a, Location &location_b);

// INPUT //////////////////////////////////////////////////////////////////////////////////
// process command line
void process_cmd_line(int argc, char** argv, Line_args &line_args);

// get locations
void get_locations(std::vector<Location> &container);

//print help
void print_help();

// FUNCTIONS //////////////////////////////////////////////////////////////////////////////
//check mst
void check_mst(std::vector<Location> &container);

//run mst
void run_mst(std::vector<Location> &container);