fork download
copy 
  1. /*Coded by::
  2.     **Avinash Tiwary**
  3.     **BE/10298/2015**
  4.     **Production Engineer**
  5.     **Producing <code>**
  6. */
  7. #include<bits/stdc++.h>
  8. #define buf ios_base::sync_with_stdio (0), cin.tie (0)
  9. typedef long long ll;
  10. typedef double dob;
  11. #define MAX 50010
  12. #define M5 509
  13. #define M6 2000009
  14. #define M 1000000007
  15. #define inf LLONG_MAX
  16. using namespace std;
  17. typedef vector<ll> V;
  18. typedef queue<ll > Q;
  19. typedef stack<ll> S;
  20. typedef pair<ll,ll> P;
  21. #define F first
  22. #define S second
  23. #define mp make_pair
  24. #define mt make_tuple
  25. #define pb push_back
  26. struct point{
  27.     ll x,y,id;
  28. };
  29. bool compx(point a, point b)  {
  30.     return a.x < b.x;
  31. }
  32. bool comp(point a, point b) {
  33.     if(a.y!=b.y)return a.y < b.y;
  34.     return a.x < b.x;
  35. }
  36. ll dis(point a,point b){
  37.     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
  38. }
  39. ll best_distance,a1,a2;
  40. void merge(point *a,point *aux,ll lo,ll mid,ll hi){
  41.     for(ll i=lo;i<=hi;i++) aux[i]=a[i];
  42.     ll i=lo,j=mid+1,k=lo;
  43.     while(i<=mid&&j<=hi){
  44.         if(comp(aux[i],aux[j])){
  45.             a[k++]=aux[i++];
  46.         }
  47.         else a[k++]=aux[j++]; 
  48.     }
  49.     while(i<=mid) a[k++]=aux[i++];
  50.     //while(j<=hi) a[k++]=aux[j++];
  51. }
  52. ll clop(point *px,point *py,point *aux,ll lo,ll hi){
  53.     if(hi<=lo) return inf;
  54.     ll mid=lo+(hi-lo)/2;
  55.     ll d1=clop(px,py,aux,lo,mid);
  56.     ll d2=clop(px,py,aux,mid+1,hi);
  57.     d1=min(d1,d2);
  58.     merge(py,aux,lo,mid,hi);
  59.     ll j=0;
  60.     for(ll i=lo;i<=hi;i++){
  61.         if(abs(py[i].x-px[mid].x)<d1) aux[j++]=py[i];
  62.     }
  63.     for(ll i=0;i<j-1;i++){
  64.         for(ll k=i+1;k<j&&aux[k].y-aux[i].y<d1;k++){
  65.             if(dis(aux[i],aux[k])<d1){
  66.                 d1=dis(aux[i],aux[k]);
  67.                 if(d1<best_distance){
  68.                     best_distance=d1;
  69.                     a1=min(aux[i].id,aux[k].id);
  70.                     a2=max(aux[i].id,aux[k].id);
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     return d1;
  76. }
  77. int main(){
  78.     buf; 
  79.     //sieve(); 
  80.     //fact();
  81.     ll i,j,k,test,flag,ans,t,n,m,a,b,c; string s1;
  82.     //cin>>test;
  83.     //test=1;
  84.     t=1;
  85.     while(t){
  86.         cin>>n;
  87.         if(n==0) break;
  88.         point *px,*py,*aux;
  89.         px= new point[n];
  90.         for(i=0;i<n;i++) {cin>>px[i].x>>px[i].y; px[i].id=i;}
  91.         py= new point[n];
  92.         sort(px,px+n,compx);
  93.         for(i=0;i<n;i++) py[i]=px[i];
  94.         best_distance=inf;
  95.         aux= new point[n];
  96.         clop(px,py,aux,0,n-1);
  97.         if(best_distance>=100000000) cout<<"INFINITY\n";
  98.         else cout<<fixed<<setprecision(4)<<sqrt(best_distance*1.0)<<"\n";
  99.         delete(px); delete(py); delete(aux);
  100.         t++;
  101.     }
  102.     return 0;
  103. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
2
1 2
2 2
0
stdout
copy 
1.0000
https://ideone.com/diWY7s
language:
C++14 (gcc 8.3)
created:
6 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!