SHARE
TWEET

ander franz - gg ok

a guest May 22nd, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define min(a, b) ((a)<(b)?(a):(b))
  6. #define MAX 9999.99999
  7.  
  8. struct Point { double x, y; };
  9. Point p[10001];
  10.  
  11. double dist(Point p1, Point p2) {
  12.     return hypot(p1.x - p2.x, p1.y - p2.y);
  13. }
  14.  
  15. int compare(const void *a, const void *b){
  16.     Point *sp1 = (Point *)a;
  17.     Point *sp2 = (Point *)b;
  18.     if (sp1->x > sp2->x) return 1;
  19.     else if (sp1->x < sp2->x) return -1;
  20.     else if (sp1->y > sp2->y) return 1;
  21.     return -1;
  22. }
  23.  
  24. double closest(long a, long b) {
  25.     double d1, d2, d, xp;
  26.     long i, j, k;
  27.    
  28.     if(a == b)
  29.         return MAX + 1.0;
  30.     else if(b - a == 1)
  31.         return dist(p[b], p[a]);
  32.     else {
  33.         int mid = (a + b) >> 1;
  34.        
  35.         d1 = closest(a, mid);
  36.         d2 = closest(mid + 1, b);
  37.        
  38.         d = min(d1, d2);
  39.  
  40.         xp = p[mid].x;
  41.        
  42.         j = mid;
  43.         do {
  44.             k = mid + 1;
  45.             while(xp - p[k].x < d && k <= b) {
  46.                 d1 = dist(p[k], p[j]);
  47.                 d = min(d, d1);
  48.                 k++;
  49.             }
  50.             j--;
  51.         } while (xp - p[j].x < d && j >= a);
  52.  
  53.     return d;
  54.     }
  55. }
  56.  
  57. int main() {
  58.     int t;
  59.     double d;
  60.     while (scanf("%d", &t), t != 0) {
  61.         for (int i = 0; i < t; i++)
  62.             scanf("%lf%lf", &p[i].x, &p[i].y);
  63.  
  64.         qsort(p, t, sizeof(p[0]), compare);
  65.  
  66.         d = closest(0, t - 1);
  67.         (d > MAX) ? puts("INFINITY") : printf("%.4lf\n", d);
  68.     }
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top