C ++ 11 — Реализация алгоритма «разделяй и властвуй» ближайших точек в переполнении стека

Я исправил проблему, переписав программу. На этот раз я не создаю вектор, отсортированный по координатам y, разбив его на части и передавая соответствующие фрагменты в рекурсивные вызовы. Вместо этого я начинаю с пустого вектора, который передается полностью до базового случая рекурсии, и там он заполняется, сортируется и передается, где он объединяется с другими векторами, которые также были заполнены таким образом. Затем соответствующие точки выбираются из этого вектора, чтобы получить полосу, которую нам нужно проверить на наличие ближайших точек, которые лежат поперек заданной медианы.

Последний вопрос, тем не менее — я продолжал получать ошибки сегментации в std :: merge, которые я не мог понять, поэтому я написал свою собственную функцию объединения, которая работала нормально … Есть идеи относительно того, откуда происходят эти ошибки? Чтобы воспроизвести их, все, что вам нужно сделать, это заменить:

Ys = mergee(leftYs, rightYs);

//merge(leftYs.begin(), leftYs.end(), rightYs.begin(), rightYs.end(), Ys.begin());

с:

//Ys = mergee(leftYs, rightYs);

merge(leftYs.begin(), leftYs.end(), rightYs.begin(), rightYs.end(), Ys.begin());

Код с генератором случайных данных для тестирования:
http://pastebin.com/yQCNh2J9

Я был бы признателен, если бы люди, которые проголосовали против, хотя бы оставили комментарий, объясняющий почему.

#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <ctime>
#include <random>

using namespace std;
using point = pair<int, int>;

bool Xcmp ( const point &c1, const point &c2 ) {
return ( c1.first < c2.first );
}

bool Ycmp ( const point &c1, const point &c2 ) {
return ( c1.second < c2.second );
}

inline ostream& operator<< ( ostream& os, const point& p ) {
return os << p.first << " " << p.second << "\n";
}

inline ostream& operator<< ( ostream& os, const vector<point> &points ) {
for( auto itr = points.begin(); itr < points.end(); itr++ ) {
os << *itr;
}
return os;
}

inline ostream& operator<< ( ostream& os, const pair<point, point> nearestPair ) {
return os << nearestPair.second.first << " " << nearestPair.second.second << "\n"<< nearestPair.first.first << " " <<  nearestPair.first.second;
}

inline double distance( const point a, const point b ) {
return sqrt( pow(( a.first - b.first ), 2 ) + pow( a.second - b.second, 2 ));
}

pair<pair<point, point>, double> bruteCP( const vector<point> &Xs, const int l, const int r ) {
pair<point, point> nearestPair;
double tempDist = 1000000000.0;
for( int i = l; i < r; i++ ) {
for( int j = i + 1; j <= r; j++ ) {
double minDist = distance( Xs[i], Xs[j] );
if( minDist < tempDist ) {
tempDist = minDist;
nearestPair = pair<point, point> ( Xs[i], Xs[j] );
}
}
}
return pair<pair<point, point>, double> (nearestPair, tempDist);
}

vector<point> makeStrip( const vector<point> Ys, int median, double minDist ) {
vector<point> strip;
for( auto it = Ys.begin(); it < Ys.end(); it++ )
if( abs((*it).first - median) < minDist ) {
strip.push_back( *it );
}
return strip;
}

vector<point> mergee(const vector<point> left, const vector<point> right) {
vector<point> result;

auto leftIterator = left.begin();
auto rightIterator = right.begin();

while(leftIterator != left.end() && rightIterator != right.end()) {
if((*leftIterator).second < (*rightIterator).second) {
result.push_back(*leftIterator);
++leftIterator;
}
else {
result.push_back(*rightIterator);
++rightIterator;
}
}
while(leftIterator != left.end()) {
result.push_back(*leftIterator);
++leftIterator;
}
while(rightIterator != right.end()) {
result.push_back(*rightIterator);
++rightIterator;
}
return result;
}

pair<pair<point, point>, double>  divConCP( const vector<point> &Xs, vector<point> &Ys, const int l, const int r ) {
int Xsize = r - l + 1;
if( Xsize <= 3 ) {
for( int i = l; i <= r; i++ ) {
Ys.push_back( Xs[i] );
}
sort( Ys.begin(), Ys.end(), Ycmp );
return bruteCP( Xs, l, r );
}

int mid =  l - 1 + (r - l + 1) / 2;
int median = Xs[mid].first;

vector<point> leftYs;
vector<point> rightYs;

auto leftClosest = divConCP( Xs, leftYs, l, mid );
auto rightClosest = divConCP( Xs, rightYs, mid + 1, r );

auto lrClosest = leftClosest.second < rightClosest.second ? leftClosest : rightClosest;

Ys = mergee(leftYs, rightYs);

//merge(leftYs.begin(), leftYs.end(), rightYs.begin(), rightYs.end(), Ys.begin());

auto strip = makeStrip( Ys, median, lrClosest.second );

for( auto itr = strip.begin(); itr < strip.end(); itr++ ) {
for( auto itr2 = itr + 1; itr2 < strip.end() && itr2 < itr + 8; itr2++ ) {
double tempDist = distance( *itr, *itr2 );
if( tempDist < lrClosest.second ) {
//cout << minDist << "\n";
//cout << *itr << " " << *itr2 << "\n";
lrClosest.second = tempDist;
lrClosest.first = pair<point, point> ( *itr, *itr2 );
}
}
}
return lrClosest;
}

int main() {
int n, x, y, MAX = 1000000000;
vector<point> Xs, Ys;
pair<int, int> minPair( -MAX, -MAX );
Xs.push_back(minPair);
//Ys.push_back(minPair);

cin >> n;
for( int i = 1; i <= n; i++ ) {
cin >> x;
cin >> y;
// x = -i;
// y = -i;

point xy( x, y );
Xs.push_back( xy );
//Ys.push_back( xy );
}

// DEBUG //
/*
n = 1000000;
srand(time(0));
std::default_random_engine gen(time(0));
std::uniform_int_distribution<int> dis(-20000000, 20000000);
for( int i = 0; i < n - 2; i++ ) {
x = dis( gen );
y = dis( gen );
//x = i;
//y = i;
point xy( x, y );
Xs.push_back( xy );
//Ys.push_back( xy );
}

Xs.push_back( point( 20001, 20001 ));
//Ys.push_back( point( 20001, 20001 ));
Xs.push_back( point( 20000, 20001 ));
//Ys.push_back( point( 20000, 20001 ));
*/
// DEBUG //

sort( Xs.begin(), Xs.end(), Xcmp );
//sort( Ys.begin(), Ys.end(), Ycmp );

auto p = divConCP( Xs, Ys, 1, n );
cout << p.first;
//bruteCP( Xs );
return 0;
}