Shortest Summation Distance [NCTU Floor 9] [Greedy + D&C]

#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

struct Point{
    int x, y;
    Point(int x, int y){
        this->x = x;
        this->y = y;
    }
};

bool compareX(Point p1, Point p2){
    return p1.x != p2.x ? (p1.x < p2.x) : (p1.y < p2.y);
}

bool compareY(Point p1, Point p2){
    return p1.y != p2.y ? (p1.y < p2.y) : (p1.x < p2.x);
}

double getLength(Point a, Point b){
    return hypot((a.x - b.x), (a.y - b.y));
}

static double mini = INT_MAX;

void solveDivideAndConquer(vector <Point> vec, double sum){
    double prevSum = sum;
    if(sum >= mini){
        return;
    }
    if(vec.size() == 2){
        sum += getLength(vec[0], vec[1]);
        mini = min(mini, sum);
        return;
    }
    for(int i = 0; i < vec.size() - 1; i++){
        for(int j = i + 1; j < vec.size(); j++){
            sum = prevSum;
            vector <Point> temp = vec;
            sum += getLength(temp[i], temp[j]);
            temp.erase(temp.begin() + j);
            temp.erase(temp.begin() + i);
            solveDivideAndConquer(temp, sum);
        }
    }
}

double solveGreedy(vector <Point> points){
    vector <bool> marked(points.size(), false);

    double sum = 0;
    for(int i = 0; i < points.size(); i++){
        if(!marked[i]){
            marked[i] = true;
            int nearest = i + 1, min_dist = -1;
            for(int j = 0; j < points.size(); j++){
                if(marked[j] || i == j)
                    continue;
                int x = points[i].x - points[j].x;
                int y = points[i].y - points[j].y;
                int m_dist = x * x + y * y;
                if(min_dist == -1 || min_dist > m_dist){
                    min_dist = m_dist;
                    nearest = j;
                }
            }
            marked[nearest] = true;
            sum += sqrt(min_dist);
        }
    }
    return sum;
}

void estimateMini(vector <Point> points){
    sort(points.begin(), points.end(), compareX);
    double min1 = solveGreedy(points);
    sort(points.begin(), points.end(), compareY);
    double min2 = solveGreedy(points);
    mini = min(min1, min2);
}

int main(){
    int n, x, y, index;
    vector <Point> points;
    string temp;
    getline(cin, temp);
    stringstream stream(temp);
    while(stream >> n){
        index = 0;
        points.reserve(2 * n);
        for(int i = 0; i < 2 * n; i++){
            stream >> x >> y;
            Point p(x, y);
            points.push_back(p);
        }
        estimateMini(points);
        if(n < 7)
            solveDivideAndConquer(points, 0);
        cout << fixed << setprecision(2) << mini << " ";
        points.clear();
    }
    return 0;
}