Advertisement
Guest User

Untitled

a guest
Apr 20th, 2015
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.84 KB | None | 0 0
  1. #include <vector>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <ctime>
  6. #include <random>
  7.  
  8. using namespace std;
  9. using point = pair<int, int>;
  10.  
  11. bool Xcmp ( const point &c1, const point &c2 ) {
  12.   return ( c1.first < c2.first );
  13. }
  14.  
  15. bool Ycmp ( const point &c1, const point &c2 ) {
  16.   return ( c1.second < c2.second );
  17. }
  18.  
  19. inline ostream& operator<< ( ostream& os, const point& p ) {
  20.   return os << p.first << " " << p.second << "\n";
  21. }
  22.  
  23. inline ostream& operator<< ( ostream& os, const vector<point> &points ) {
  24.   for( auto itr = points.begin(); itr < points.end(); itr++ ) {
  25.     os << *itr;
  26.   }
  27.   return os;
  28. }
  29.  
  30. inline ostream& operator<< ( ostream& os, const pair<point, point> nearestPair ) {
  31.   return os << nearestPair.second.first << " " << nearestPair.second.second << "\n"
  32.             << nearestPair.first.first << " " <<  nearestPair.first.second;
  33. }
  34.  
  35. inline double distance( const point a, const point b ) {
  36.   return sqrt( pow(( a.first - b.first ), 2 ) + pow( a.second - b.second, 2 ));
  37. }
  38.  
  39. pair<pair<point, point>, double> bruteCP( const vector<point> &Xs, const int l, const int r ) {
  40.   pair<point, point> nearestPair;
  41.   double tempDist = 1000000000.0;
  42.   for( int i = l; i < r; i++ ) {
  43.     for( int j = i + 1; j <= r; j++ ) {
  44.       double minDist = distance( Xs[i], Xs[j] );
  45.       if( minDist < tempDist ) {
  46.         tempDist = minDist;
  47.         nearestPair = pair<point, point> ( Xs[i], Xs[j] );
  48.       }
  49.     }
  50.   }
  51.   return pair<pair<point, point>, double> (nearestPair, tempDist);
  52. }
  53.  
  54. vector<point> makeStrip( const vector<point> Ys, int median, double minDist ) {
  55.   vector<point> strip;
  56.   for( auto it = Ys.begin(); it < Ys.end(); it++ )
  57.     if( abs((*it).first - median) < minDist ) {
  58.       strip.push_back( *it );
  59.     }
  60.     return strip;
  61. }
  62.  
  63. vector<point> mergee(const vector<point> left, const vector<point> right) {
  64.   vector<point> result;
  65.  
  66.   auto leftIterator = left.begin();
  67.   auto rightIterator = right.begin();
  68.  
  69.   while(leftIterator != left.end() && rightIterator != right.end()) {
  70.     if((*leftIterator).second < (*rightIterator).second) {
  71.         result.push_back(*leftIterator);
  72.         ++leftIterator;
  73.     }
  74.     else {
  75.         result.push_back(*rightIterator);
  76.         ++rightIterator;
  77.     }
  78.   }
  79.   while(leftIterator != left.end()) {
  80.     result.push_back(*leftIterator);
  81.     ++leftIterator;
  82.   }
  83.   while(rightIterator != right.end()) {
  84.     result.push_back(*rightIterator);
  85.     ++rightIterator;
  86.   }
  87.   return result;
  88. }
  89.  
  90. pair<pair<point, point>, double>  divConCP( const vector<point> &Xs, vector<point> &Ys, const int l, const int r ) {
  91.   int Xsize = r - l + 1;
  92.   if( Xsize <= 3 ) {
  93.     for( int i = l; i <= r; i++ ) {
  94.       Ys.push_back( Xs[i] );
  95.     }
  96.     sort( Ys.begin(), Ys.end(), Ycmp );
  97.     return bruteCP( Xs, l, r );
  98.   }
  99.  
  100.   int mid =  l - 1 + (r - l + 1) / 2;
  101.   int median = Xs[mid].first;
  102.  
  103.   vector<point> leftYs;
  104.   vector<point> rightYs;
  105.  
  106.   auto leftClosest = divConCP( Xs, leftYs, l, mid );
  107.   auto rightClosest = divConCP( Xs, rightYs, mid + 1, r );
  108.  
  109.   auto lrClosest = leftClosest.second < rightClosest.second ? leftClosest : rightClosest;
  110.  
  111.   Ys = mergee(leftYs, rightYs);
  112.  
  113.   //merge(leftYs.begin(), leftYs.end(), rightYs.begin(), rightYs.end(), Ys.begin());
  114.  
  115.   auto strip = makeStrip( Ys, median, lrClosest.second );
  116.  
  117.   for( auto itr = strip.begin(); itr < strip.end(); itr++ ) {
  118.     for( auto itr2 = itr + 1; itr2 < strip.end() && itr2 < itr + 8; itr2++ ) {
  119.       double tempDist = distance( *itr, *itr2 );
  120.       if( tempDist < lrClosest.second ) {
  121.         //cout << minDist << "\n";
  122.         //cout << *itr << " " << *itr2 << "\n";
  123.         lrClosest.second = tempDist;
  124.         lrClosest.first = pair<point, point> ( *itr, *itr2 );
  125.       }
  126.     }
  127.   }
  128.   return lrClosest;
  129. }
  130.  
  131. int main() {
  132.   int n, x, y, MAX = 1000000000;
  133.   vector<point> Xs, Ys;
  134.   pair<int, int> minPair( -MAX, -MAX );
  135.   Xs.push_back(minPair);
  136.   //Ys.push_back(minPair);
  137.  
  138.   cin >> n;
  139.   for( int i = 1; i <= n; i++ ) {
  140.     cin >> x;
  141.     cin >> y;
  142.    // x = -i;
  143.    // y = -i;
  144.  
  145.     point xy( x, y );
  146.     Xs.push_back( xy );
  147.     //Ys.push_back( xy );
  148.   }
  149.  
  150.     // DEBUG //
  151. /*
  152.    n = 1000000;
  153.    srand(time(0));
  154.    std::default_random_engine gen(time(0));
  155.    std::uniform_int_distribution<int> dis(-20000000, 20000000);
  156.    for( int i = 0; i < n - 2; i++ ) {
  157.      x = dis( gen );
  158.      y = dis( gen );
  159.      //x = i;
  160.      //y = i;
  161.      point xy( x, y );
  162.      Xs.push_back( xy );
  163.      //Ys.push_back( xy );
  164.    }
  165.  
  166.      Xs.push_back( point( 20001, 20001 ));
  167.      //Ys.push_back( point( 20001, 20001 ));
  168.      Xs.push_back( point( 20000, 20001 ));
  169.      //Ys.push_back( point( 20000, 20001 ));
  170. */
  171.   // DEBUG //
  172.  
  173.   sort( Xs.begin(), Xs.end(), Xcmp );
  174.   //sort( Ys.begin(), Ys.end(), Ycmp );
  175.  
  176.   auto p = divConCP( Xs, Ys, 1, n );
  177.   cout << p.first;
  178.   //bruteCP( Xs );
  179.   return 0;
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement