fork(2) download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. #define x second
  10. #define y first
  11.  
  12. typedef pair<long long, long long> pll;
  13.  
  14. inline double dist(pll p1, pll p2)
  15. {
  16.     return sqrt((double) (p2.y - p1.y)*(p2.y - p1.y) + (p2.x - p1.x)*(p2.x - p1.x));
  17. }
  18.  
  19.  
  20. int main(int argc, const char * argv[])
  21. {
  22.     int numPoints;
  23.     cin >> numPoints;
  24.  
  25.     vector <pll> points;
  26.     points.resize(numPoints);
  27.  
  28.     for (int i = 0; i < numPoints; i++)
  29.     {
  30.         cin >> points[i].x >> points[i].y;
  31.     }
  32.  
  33.     //Sorts the points by y coordinate (because y is first)
  34.     sort(points.begin(), points.end());
  35.  
  36.     double shortestDistSoFar = INFINITY;
  37.     set <pll> boundingBox; //Bounding box maintained by y-coordinate
  38.     boundingBox.insert(points[0]);
  39.  
  40.     int left = 0;
  41.  
  42.     pll best1, best2;
  43.  
  44.     for (int i = 1; i < numPoints; i++)
  45.     {
  46.         //Maintain only points to the left of the current point whose distance is less than bestDist
  47.         while ((left < i) && (points[i].x - points[left].x > shortestDistSoFar))
  48.         {
  49.             boundingBox.erase(points[left]);
  50.             left++;
  51.         }
  52.  
  53.         //Consider only points within bestDist of the current point
  54.         for (auto it = boundingBox.lower_bound(pll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar));
  55.              it != boundingBox.end() && it->y <= points[i].y + shortestDistSoFar; it++)
  56.         {
  57.             if (dist(*it, points[i]) < shortestDistSoFar)
  58.             {
  59.                 shortestDistSoFar = dist(*it, points[i]);
  60.                 best1 = *it;
  61.                 best2 = points[i];
  62.             }
  63.         }
  64.  
  65.         boundingBox.insert(points[i]);
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
  71.  
Runtime error #stdin #stdout #stderr 0s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Gate9h
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!