I'm trying to solve this problem by bruteforce, but it seems to run very slow when given 7 (which is 2*7 points).
Note: I only need to run it to maximum 2*8 points
Problem statement:
Given 2*N points in a 2d plane, connect them in pairs to form N line segments. Minimize the total length of all the line segments.
Example:
Input: 5 10 10 20 10 5 5 1 1 120 3 6 6 50 60 3 24 6 9 0 0
Output: 118.4
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
class point{
public:
double x, y;
};
double getLength(point a, point b){
return hypot((a.x - b.x), (a.y - b.y));
}
static double mini = INT_MAX;
void solve(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);
solve(temp, sum);
}
}
}
int main(){
point temp;
int input;
double sum = 0;
cin >> input;
vector<point> vec;
for(int i = 0; i < 2 * input; i++){
cin >> temp.x >> temp.y;
vec.push_back(temp);
}
solve(vec, sum);
cout << fixed << setprecision(2) << mini << endl;
}
How can I speed up this code ?
temp.erase()
, which probably spends most of its time doing the equivalent of amemmove()
.mini
is large, and then initially the process of eliminating the obvious bad solutions with the testif (sum > mini)
is not efficient. For example, try first to better estimate it, for example by trying first a greedy algorithm to initialize this valuemini
std::hypot
is part of numerics library. One another inconvenient ofusing namespace std