fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 100010
  4. #define INF 10000000000000000
  5.  
  6.  
  7.  
  8.  
  9. typedef long long int ll;
  10.  
  11. ll sum[100010];
  12.  
  13.  
  14.  
  15. struct point
  16. {
  17.     ll x,y;
  18. } jibon[MAX+5],maneNai[MAX+5];
  19.  
  20.  
  21.  
  22. bool cmp(struct point p, struct point q)
  23. {
  24.     if(p.y<q.y) return true;
  25.     else return false;
  26. }
  27.  
  28. ll bruteForce(point p, point q)
  29. {
  30.     return ((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
  31. }
  32.  
  33. point strip[MAX+10];
  34. int flag[MAX+5];
  35.  
  36. ll closestPair(point px[], int st, int en)
  37. {
  38.     if((en-st+1)>=3)
  39.    {
  40.      int mid = (st+en)/2;
  41.      ll d = min(closestPair(px,st,mid),closestPair(px,mid+1,en));
  42.      int j=0;
  43.      for(int i=mid;i>=st;i--)
  44.      {
  45.          if((px[mid].x-px[i].x)<d)
  46.          {
  47.             j++;
  48.             strip[j]=px[i];
  49.          }
  50.          else break;
  51.      }
  52.      for(int i=mid+1;i<=en;i++)
  53.      {
  54.          if((px[i].x-px[mid].x)<d)
  55.          {
  56.              j++;
  57.              strip[j]=px[i];
  58.          }
  59.      }
  60.      sort(strip+1,strip+1+j,cmp);
  61.      for(int i=1;i<=j;i++)
  62.      {
  63.  
  64.  
  65.          for(int k=i+1;k<=j;k++)
  66.          {
  67.             if((strip[k].y-strip[i].y)<d)
  68.             {
  69.                 d = min(d,bruteForce(strip[i],strip[k]));
  70.             }
  71.             else break;
  72.          }
  73.  
  74.      }
  75.      return d;
  76.    }
  77.    else
  78.    {
  79.       ll d = INF;
  80.       for(int i=st;i<=en;i++)
  81.       {
  82.           for(int k=i+1;k<=en;k++)
  83.           {
  84.             d = min(d,bruteForce(px[i],px[k]));
  85.           }
  86.       }
  87.       return d;
  88.    }
  89. }
  90.  
  91.  
  92. int main()
  93. {
  94.     ll n;
  95.  
  96.     cin>>n;
  97.     sum[0] = 0;
  98.     for(int i=1;i<=n;i++)
  99.     {
  100.         ll v;
  101.         cin>>v;
  102.         sum[i] = sum[i-1]+v;
  103.         jibon[i].x = i;
  104.         jibon[i].y = sum[i];
  105.     }
  106.     ll v = 0;
  107.     v = closestPair(jibon,1,n);
  108.     cout<<v<<endl;
  109.  
  110.     return 0;
  111.  
  112. }
  113.  
Runtime error #stdin #stdout 0s 21928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C7lW94
language:
C++14 (gcc 8.3)
created:
6 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!