Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement