#include "poke.h"
#include <iomanip>

using namespace std;

class Primary {

    private:
        bool MST;
        bool FASTTSP;
        bool OPTTSP;
        double upperBound;
        double lowerBound;
        vector<fast> inputV;
        vector<arbitrary> yoster2;
        vector<int> spots;
        vector<int> bestPath;
        vector<NarrowNode> inputVector2;
        double currentDistance;
        double bestDistance;

    public:
        void set_opttsp_defaults() {
            upperBound = 0;
            currentDistance = 0;
            lowerBound = 0;
            bestDistance = 0;
        }

        void set_defaults() {
            MST = false;
            FASTTSP = false;
            OPTTSP = false;
        }

        void help_option() {
            cout << "For more information, please read the README file." << endl;
            exit(0);
        }

        void option_management(int argc, char *argv[])
        {
            string mode;
            opterr = false;
            int choice;
            int option_index = 0;
            // getOps.h required statements
            option longOpts[] = {
            { "mode", required_argument, nullptr, 'm' },
            { "help", no_argument, nullptr, 'h'},
            { nullptr, 0, nullptr, '\0' }}; // Required closing bit

            while ((choice = getopt_long(argc, argv, "m:h", longOpts, &option_index)) != -1) {
            switch (choice) {
                case 'm': {
                    mode = optarg;
                    if(mode == "MST") {
                        MST = true;
                        break;
                    } else if(mode == "FASTTSP") {
                        FASTTSP = true;
                        break;
                    } else if(mode == "OPTTSP") {
                        OPTTSP = true;
                        break;
                    } else {
                        cerr << "Invalid mode" << endl;
                        exit(1);
                    }
                } // end case m
                case 'h': {
                    help_option();
                    break;
                } // end case h
                default:
                    cerr << "Unknown command line option" << endl;
                    exit(1);
                } // End of Switch
             } // End of While
            } // end of option_management()

        void mst_input_management() {
                // Input vector
                vector<Node> inputVector; 
            
                // Initializing number of vertices for the for loop
                int numVertex;
                cin >> numVertex;

                // Reserving vector space 
                inputVector.reserve(numVertex);

                // Taking in input values and pushing them into the whole vector
                for(int i = 0; i < numVertex; i++) {
                    int x, y;
                    Node toBePushed;
                    cin >> x >> y;
                    toBePushed.x = x;
                    toBePushed.y = y;
                    type_terrain(toBePushed);
                    inputVector.push_back(toBePushed);
                }

                prims_algorithm(inputVector);

            }

        void prims_algorithm(vector<Node> &inputVector) {
                int numVertex = static_cast<int>(inputVector.size());

                vector<Prim> primVector;
                primVector.reserve(numVertex);
                primVector.resize(numVertex);

                // Setting an arbitrary node to the starting point and marking
                // it's distance 0
                primVector[0].distance = 0;

                int count = 0;
                double totalCost = 0;
                for(count = 0; count < numVertex; count++) {
                    // Finding smallest false
                    double bestDistance = std::numeric_limits<double>::infinity();
                    int bestIndex = -1;
                    for(int i = 0; i < numVertex; i++) {
                        if(primVector[i].visited == false && primVector[i].distance < bestDistance) {
                            double tempDistance = primVector[i].distance;
                            bestIndex = i;
                            bestDistance = tempDistance;
                        }
                    }
                    // Mark as true
                    primVector[bestIndex].visited = true;
                    // Update false ones if they're closer to bestIndex than what's in the table
                    for(int i = 0; i < numVertex; i++) {
                        if(primVector[i].visited == false) {
                           double closeDistance = mst_distance_function(inputVector[i], inputVector[bestIndex]);
                           if(closeDistance < primVector[i].distance) {
                               primVector[i].distance = closeDistance;
                               primVector[i].previous = bestIndex;
                           }
                        }
                    }
                }
                for(int i = 0; i < numVertex; i++) {
                    if(primVector[i].visited) {
                        totalCost = totalCost + sqrt(primVector[i].distance);
                    }
                }

                cout << totalCost << endl;

                for(int i = 1; i < numVertex; i++) {
                    if(primVector[i].previous >= i) {
                        cout << i << " " << primVector[i].previous << endl;
                    } else {
                        cout << primVector[i].previous << " " << i << endl;
                    }
                }
            }

        double mst_distance_function(Node &one, Node &two) {
                if(one.terrain == Node::Terrain::land 
                && two.terrain == Node::Terrain::sea) {
                    return std::numeric_limits<double>::infinity();
                } else if(one.terrain == Node::Terrain::sea
                && two.terrain == Node::Terrain::land) {
                    return std::numeric_limits<double>::infinity();
                } else if((one.x == two.x) && (one.y == two.y)) {
                    return 0;
                } else {
                    double firstSquare, secondSquare, added, firstSubtract, secondSubtract;
                    firstSubtract = static_cast<double>(one.x) - static_cast<double>(two.x);
                    secondSubtract = static_cast<double>(one.y) - static_cast<double>(two.y);
                    firstSquare = firstSubtract * firstSubtract;
                    secondSquare = secondSubtract * secondSubtract; 
                    added = firstSquare + secondSquare;
                    // Returning sum of squares and delaying the square root
                    return static_cast<double>(added);
                }
            }

        void type_terrain(Node &pushed) {
                // Function to initialize terrain in the Node object
                if(pushed.x < 0 && pushed.y < 0) {
                    pushed.terrain = Node::Terrain::sea;
                } else if(pushed.x == 0 && pushed.y < 0) {
                    pushed.terrain = Node::Terrain::coast;
                } else if(pushed.x < 0 && pushed.y == 0) {
                    pushed.terrain = Node::Terrain::coast;
                } else {
                    pushed.terrain = Node::Terrain::land;
                }
            }

        void fast_tsp_input_management() {
                // Input vector
                vector<fast> inputVector; 
            
                // Initializing number of vertices for the for loop
                int numVertex;
                cin >> numVertex;

                // Reserving vector space 
                inputVector.reserve(numVertex);

                // Taking in input values and pushing them into the whole vector
                for(int i = 0; i < numVertex; i++) {
                    int x, y;
                    fast toBePushed;
                    cin >> x >> y;
                    toBePushed.x = x;
                    toBePushed.y = y;
                    inputVector.push_back(toBePushed);
                }
                arbitrary_insertion(inputVector);
        }

        void arbitrary_insertion(vector<fast> &inputVector) {

            size_t numVertex = inputVector.size();

            vector<arbitrary> yoster;
            int ctr = 0;

            // Starting with first vertex
            inputVector[0].visited = true;
            arbitrary b;
            b.first = 0;

            // Identiying the vertex j that is the minimum and setting the tour to i->j->i
            double minDistance = std::numeric_limits<double>::infinity();
            size_t valueOfJ = -1;

            for(size_t j = 1; j < static_cast<size_t>(numVertex); j++) {
                double temp = fast_tsp_distance_function(inputVector[0], inputVector[j]);
                if(temp < minDistance) {
                    minDistance = temp;
                    valueOfJ = j;
                }
            }
            b.second = static_cast<int>(valueOfJ);
            yoster.push_back(b);
            ctr = 1;
            inputVector[valueOfJ].visited = true;

            // Arbitrarily pick a vertex k not in partial tour 
            int yosterToBreak = -1;
            for(size_t i = 0; i < numVertex; i++) {
                if(inputVector[i].visited == true) {
                    continue;
                } 
                // Identifying the edge where the partial path is minimized 
                double minEdge = std::numeric_limits<double>::infinity();
                for(int j = 0; j < static_cast<int>(yoster.size()); j++) {
                    double tempDistance = fast_tsp_minimization_formula(inputVector, yoster, j, static_cast<int>(i));
                    if(tempDistance < minEdge) {
                        minEdge = tempDistance;  
                        yosterToBreak = j;
                    }   
                }
                // totalDistance += minEdge;
                auto it = yoster.begin() + yosterToBreak + 1;

                arbitrary a;
                a.first = static_cast<int>(i);
                a.second = yoster[yosterToBreak].second;
                yoster[yosterToBreak].second = static_cast<int>(i);
                yoster.insert(it, a);
                inputVector[i].visited = true;
                ctr++;
            }
            
            double totalDistance = 0;
            for(size_t i = 0; i < yoster.size(); i++) {
                totalDistance += sqrt(fast_tsp_distance_function(inputVector[yoster[i].first], inputVector[yoster[i].second]));
            }
            totalDistance += sqrt(fast_tsp_distance_function(inputVector[yoster[yoster.size()-1].second], inputVector[yoster[0].first]));
            
            cout << totalDistance << endl;

            for(size_t i = 0; i < static_cast<size_t>(ctr); i++) {
                cout << yoster[i].first << " ";
            }
            cout << yoster[yoster.size()-1].second << " ";
            cout << endl;
            
        }

        double fast_tsp_minimization_formula(vector<fast> &inputVector, vector<arbitrary> &yoster, int i, int k) {
            double firstLength = fast_tsp_distance_function(inputVector[yoster[i].first], inputVector[k]);
            double secondLength = fast_tsp_distance_function(inputVector[yoster[i].second], inputVector[k]);
            double thirdLength = fast_tsp_distance_function(inputVector[yoster[i].first], inputVector[yoster[i].second]);
            double final = firstLength + secondLength - thirdLength;
            return final;
        }
        
        double fast_tsp_distance_function(fast &one, fast &two) {

            double firstSquare, secondSquare, added, firstSubtract, secondSubtract;
            firstSubtract = static_cast<double>(one.x) - static_cast<double>(two.x);
            secondSubtract = static_cast<double>(one.y) - static_cast<double>(two.y);
            firstSquare = firstSubtract * firstSubtract;
            secondSquare = secondSubtract * secondSubtract; 
            added = firstSquare + secondSquare;
            // Returning sum of squares and delaying the square root
            return static_cast<double>(added);
        }
        
        void optimal_tsp() {
            set_opttsp_defaults();
            optimal_tsp_input_management();
            for(size_t i = 0; i < yoster2.size(); i++) {
                spots.push_back(yoster2[i].first);
            }
            spots.push_back(yoster2[yoster2.size()-1].second);
            size_t x = 1;
            bestDistance = upperBound;

            for(int i = 0; i < 11; i++) {
                spots[i] = i;
            }

            genPerms(spots, x);

            cout << bestDistance << endl;
            return;
        }

        void optimal_tsp_input_management() {
            // Initializing number of vertices for the for loop
            int numVertex;
            cin >> numVertex;

            // Reserving vector space 
            inputV.reserve(numVertex);

            // Taking in input values and pushing them into the whole vector
            for(int i = 0; i < numVertex; i++) {
                int x, y;
                fast toBePushed;
                cin >> x >> y;
                toBePushed.x = x;
                toBePushed.y = y;
                inputV.push_back(toBePushed);
            }

            size_t numV = inputV.size();

            int ctr = 0;

            // Starting with first vertex
            inputV[0].visited = true;
            arbitrary b;
            b.first = 0;

            // Identiying the vertex j that is the minimum and setting the tour to i->j->i
            double minDistance = std::numeric_limits<double>::infinity();
            size_t valueOfJ = -1;

            for(size_t j = 1; j < static_cast<size_t>(numV); j++) {
                double temp = fast_tsp_distance_function(inputV[0], inputV[j]);
                if(temp < minDistance) {
                    minDistance = temp;
                    valueOfJ = j;
                }
            }
            b.second = static_cast<int>(valueOfJ);
            yoster2.push_back(b);
            ctr = 1;
            inputV[valueOfJ].visited = true;

            // Arbitrarily pick a vertex k not in partial tour 
            int yosterToBreak = -1;
            for(size_t i = 0; i < numV; i++) {
                if(inputV[i].visited == true) {
                    continue;
                } 
                // Identifying the edge where the partial path is minimized 
                double minEdge = std::numeric_limits<double>::infinity();
                for(int j = 0; j < static_cast<int>(yoster2.size()); j++) {
                    double tempDistance = fast_tsp_minimization_formula(inputV, yoster2, j, static_cast<int>(i));
                    if(tempDistance < minEdge) {
                        minEdge = tempDistance;  
                        yosterToBreak = j;
                    }   
                }

                auto it = yoster2.begin() + yosterToBreak + 1;

                arbitrary a;
                a.first = static_cast<int>(i);
                a.second = yoster2[yosterToBreak].second;
                yoster2[yosterToBreak].second = static_cast<int>(i);
                yoster2.insert(it, a);
                inputV[i].visited = true;
                ctr++;
            }
                
            for(size_t i = 0; i < yoster2.size(); i++) {
                upperBound += sqrt(fast_tsp_distance_function(inputV[yoster2[i].first], inputV[yoster2[i].second]));
            }
            upperBound += sqrt(fast_tsp_distance_function(inputV[yoster2[yoster2.size()-1].second], inputV[yoster2[0].first]));
            return;
        }

        bool promising(vector<int> &path, size_t permLength) {
            size_t remaining = 0;
            remaining = path.size() - permLength;
            if(remaining < 6) {
                return true;
            } else {
                lowerBound = mst_opt_tsp(path, permLength);
                if(lowerBound >= bestDistance) {
                    return false;
                }
                double x = lowerBound;
                double minArmOne = 0;
                double tempInf = std::numeric_limits<double>::infinity();
                double tempInf2 = std::numeric_limits<double>::infinity();
                double minArmTwo = 0;

                for(size_t i = 0; i < path.size(); i++) {
                    if(i <= permLength) {
                        continue;
                    }
                    if(tempInf > sqrt(other_mst_distance_function(inputV[path[0]], inputV[path[i]]))) {
                        tempInf = sqrt(other_mst_distance_function(inputV[path[0]], inputV[path[i]]));
                        minArmOne = tempInf;
                    }
                }
                for(size_t i = 0; i < path.size(); i++) {
                    if(i <= permLength) {
                        continue;
                    }
                    if(tempInf2 > sqrt(other_mst_distance_function(inputV[path[permLength-1]], inputV[path[i]]))) {
                        tempInf2 = sqrt(other_mst_distance_function(inputV[path[permLength-1]], inputV[path[i]]));
                        minArmTwo = tempInf2;
                    }
                }
                lowerBound += minArmOne;
                lowerBound += minArmTwo;
                lowerBound += currentDistance;

                bool temp;

                if(lowerBound > upperBound) {
                    temp = false;
                } else {
                    temp = true;
                }
                for (size_t i = 0; i < path.size(); ++i) {
                    cout << setw(2) << path[i] << ' ';
                }
                    cout << setw(4) << permLength << setw(10) << currentDistance;
                    cout << setw(10) << minArmOne << setw(10) << minArmTwo;
                    cout << setw(10) << x << setw(10) << lowerBound << "  " << temp << '\n';


                
                if(lowerBound > bestDistance) {
                    return false;
                }
                return true;
            }
        }

        double other_mst_distance_function(fast &one, fast &two) {
            double firstSquare, secondSquare, added, firstSubtract, secondSubtract;
            firstSubtract = static_cast<double>(one.x) - static_cast<double>(two.x);
            secondSubtract = static_cast<double>(one.y) - static_cast<double>(two.y);
            firstSquare = firstSubtract * firstSubtract;
            secondSquare = secondSubtract * secondSubtract; 
            added = firstSquare + secondSquare;
            // Returning sum of squares and delaying the square root
            return static_cast<double>(added);
        }

        void genPerms(vector<int> &path, size_t permLength) {
            if (permLength == path.size()) {
                double finalDist = 0;
                for(size_t i = 0; i < path.size()-1; i++) {
                    finalDist = finalDist + sqrt(other_mst_distance_function(inputV[path[i]], inputV[path[i+1]]));
                }
                finalDist += sqrt(other_mst_distance_function(inputV[path[0]], inputV[path[path.size()-1]]));
                if(finalDist <= bestDistance) {
                    bestDistance = finalDist;
                    bestPath.reserve(path.size());
                    for(size_t i = 0; i < path.size(); i++) {
                        bestPath[i] = path[i];
                    }
                }
                return;
            } // if
            if (!promising(path, permLength))
                return;
            for (size_t i = permLength; i < path.size(); ++i) {
                swap(path[permLength], path[i]);
                update(permLength, true, path);
                // updpate
                genPerms(path, permLength + 1);
                update(permLength, false, path);
                swap(path[permLength], path[i]);
            } // for
        } // genPerms()
   
        void update(size_t permLength, bool reduce, vector<int> &path) {
            if(reduce) {
                for(size_t i = 0; i < permLength; i++) {
                    currentDistance += sqrt(other_mst_distance_function(inputV[path[i]], inputV[path[i+1]]));
                }
            } else {
                for(size_t i = 0; i < permLength; i++) {
                    currentDistance -= sqrt(other_mst_distance_function(inputV[path[i]], inputV[path[i+1]]));
                }
            }

        } 
        
        double mst_opt_tsp(vector<int> &path, size_t permLength) {
            int numVertex = static_cast<int>(path.size());

            // Initialize vector of prim objects 
            vector<Prim> primVector;
            primVector.reserve(numVertex);
            primVector.resize(numVertex);

            // Setting an arbitrary node to the starting point and marking
            // it's distance 0
            primVector[permLength].distance = 0;

            // Looping and doing the actual algorithm
            double totalCost = 0;
            for(size_t count = static_cast<int>(permLength); count < path.size(); count++) {
                // Finding smallest false
                double bestDistance = std::numeric_limits<double>::infinity();
                int bestIndex = -1;
                for(size_t i = permLength; i < path.size(); i++) {
                    //double tempDistance = mst_distance_function(inputVector[count], inputVector[i]);
                    if(primVector[i].visited == false && primVector[i].distance < bestDistance) {
                        double tempDistance = primVector[i].distance;
                        bestIndex = static_cast<int>(i);
                        bestDistance = tempDistance;
                    }
                }
                // Mark as true
                primVector[bestIndex].visited = true;
                // Update false ones if they're closer to bestIndex than what's in the table
                for(size_t i = permLength; i < path.size(); i++) {
                    if(primVector[i].visited == false) {
                        double closeDistance = other_mst_distance_function(inputV[path[i]], inputV[path[bestIndex]]);
                        if(closeDistance < primVector[i].distance) {
                            primVector[i].distance = closeDistance;
                            primVector[i].previous = bestIndex;
                        }
                    }
                }
            }
            for(size_t i = permLength; i < path.size(); i++) {
                if(primVector[i].visited) {
                    totalCost = totalCost + sqrt(primVector[i].distance);
                }
            }

            return totalCost;
        }
     
        bool get_mst() {
            return MST;
        }

        bool get_fasttsp() {
            return FASTTSP;
        }

        bool get_opttsp() {
            return OPTTSP;
        }
};

int main(int argc, char *argv[]) {
    cout << fixed << showpoint << setprecision(2);
    // Precision output required lines
    std::cout << std::setprecision(2);
    std::cout << std::fixed;

    // I/O Speedup
    ios_base::sync_with_stdio(false);

    // Declaring and initializing an instance of the primary class
    Primary p1;
    p1.set_defaults();
    p1.option_management(argc, argv);
    if(p1.get_mst()) {
        p1.mst_input_management();
        return 0;
    } else if(p1.get_fasttsp()) {
        p1.fast_tsp_input_management();
        return 0;
    } else {
        p1.optimal_tsp();
        return 0;
    }

    return 0;
}