fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int u;
  4. int v;
  5. long long int bestmin = 10000000000000;
  6. long long int minimum = 10000000000000;
  7. struct points
  8. {
  9.     long long int x;
  10.     long long int y;
  11.     int pos;
  12. };
  13. int xcompare(points a, points b)
  14. {
  15.     return(a.x < b.x);
  16. }
  17. int ycompare(points a, points b)
  18. {
  19.     return (a.y < b.y);
  20. }
  21. long long int dis(points a,points b)
  22. {
  23.  
  24.     return (((a.x - b .x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));
  25.  
  26. }
  27. long long int brute(points a[],int s,int e)
  28. {
  29.     int i;
  30.     int j;
  31.     int n;
  32.     int c;
  33.     int d;
  34.     int l;
  35.     int r;
  36.     n = e - s + 1;
  37.  
  38.     for(i = s; i <= e ; i++) {
  39.         for(j = i + 1; j <= e; j++) {
  40.             if(dis(a[i],a[j]) < minimum) {
  41.                 minimum = dis(a[i],a[j]);
  42.                 if(minimum < bestmin) {
  43.                     bestmin = minimum;
  44.                     u = a[i].pos;
  45.                     v = a[j].pos;
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     return minimum;
  52. }
  53. long long int findclose(points a[],int k, long long int d)
  54. {
  55.  
  56.  
  57.     int i;
  58.     int j;
  59.     long long int min;
  60.     min = d;
  61.  
  62.     sort(a,a+k,ycompare);
  63.  
  64.  
  65.     for(i = 0; i < k; i++) {
  66.         for(j = i + 1; j < k && (a[j].y - a[i].y) < min; j++) {
  67.             if(dis(a[i],a[j]) < min) {
  68.                 min = dis(a[i],a[j]);
  69.                 if(min < bestmin) {
  70.                     bestmin = min;
  71.                     u = a[i].pos;
  72.                     v = a[j].pos;
  73.                 }
  74.  
  75.             }
  76.         }
  77.     }
  78.  
  79.     return min;
  80. }
  81. long long int  closepoints(points a[],int s, int e)
  82. {
  83.     int n = e - s + 1;
  84.  
  85.  
  86.  
  87.     int mid = (s + e) / 2;
  88.     int mid1 = a[mid].x;
  89.     if(n <= 3) {
  90.        return  brute(a,s,e);
  91.     }
  92.  
  93.     long long int l = closepoints(a,s,mid);
  94.     long long int r = closepoints(a,mid + 1,e);
  95.     //cout<<l<<' '<<r<<endl;
  96.  
  97.     long long int m = min(l,r);
  98.  
  99.     points b[n];
  100.     int k;
  101.     int i;
  102.  
  103.     //cout<<mid1<<endl;
  104.     k = 0;
  105.  
  106.     for(i = s; i <= e; i++) {
  107.         if(abs(mid1 - a[i].x) < m) {
  108.             b[k] = a[i];
  109.             k++;
  110.  
  111.             //cout<<i<<endl;
  112.         }
  113.     }
  114.  
  115.  
  116.     return min(m,findclose(b,k,m));
  117.  
  118. }
  119. int main()
  120. {
  121.     int n;
  122.     points a[50006];
  123.     int i;
  124.  
  125.     cout << setiosflags(ios::fixed) << setprecision(6);
  126.  
  127.     cin>>n;
  128.     for(i = 0; i < n; i++) {
  129.         cin>>a[i].x>>a[i].y;
  130.         a[i].pos = i;
  131.     }
  132.  
  133.     sort(a,a+n,xcompare);
  134.  
  135.  
  136.     closepoints(a,0,n-1);
  137.     if(u > v) {
  138.         swap(u,v);
  139.     }
  140.     cout<<u<<' '<<v<<' '<<sqrt((double)bestmin)<<endl;
  141. }
  142.  
  143.  
Success #stdin #stdout 0s 4004KB
comments (?)
stdin
copy 
5
0 0
-4 1
-7 -2
4 5
1 1
stdout
copy 
0 4 1.414214
https://ideone.com/5CYz72
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!