链接：https://www.nowcoder.com/acm/contest/59/E
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
64bit IO Format: %lld
题目描述
给你一个长为n的序列a
定义f(i,j)=(i-j)2+g(i,j)2
g是这样的一个函数
求最小的f(i,j)的值，i!=j
输入描述:
第一行一个数n
之后一行n个数表示序列a
输出描述:
输出一行一个数表示答案
输入例子:
4
1 0 0 -1
输出例子:
1
-->
示例1
输入
4
1 0 0 -1
输出
1
备注:
对于100%的数据，2 <= n <= 100000 , |ai| <= 10000
//////////////////////////////////////////////////////////////////////////////////////////////////
用前缀和s[i]做y值，i做x值，问题等价与求平面最近点对之间的距离
放两个找的别人的平面最近点对的证明
https://www.zhihu.com/question/24755395
http://blog.csdn.net/yql_water/article/details/45939653
自己的代码是借鉴后面那个blog的
///////////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define mst(a,b) memset((a),(b), sizeof a)
#define lowbit(a) ((a)&(-a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+;
const int maxn=1e5+;
struct node{
int x,y;
bool operator<(const node&p)const{return x<p.x;}
}a[maxn];
ll dis(int L,int R){
return (ll)(a[L].x-a[R].x)*(a[L].x-a[R].x)+(ll)(a[L].y-a[R].y)*(a[L].y-a[R].y);
}
ll dfs(int L,int R,vector<int>&t){
if(R-L<=){
if(R==L){t.PB(L);return INF;}
if(a[L].y>a[R].y)t.PB(R),t.PB(L);
else t.PB(L),t.PB(R);
return dis(L,R);
}
vector<int>tl,tr;
int mid=(L+R)>>;
ll mm=min(dfs(L,mid,tl),dfs(mid+,R,tr));
int i=,j=,n=tl.size(),m=tr.size();
while(i<n||j<m){
if(j>=m||i<n&&a[tl[i]].y<a[tr[j]].y)t.PB(tl[i++]);
else t.PB(tr[j++]);
}
for(i=;i<t.size();++i)for(j=;j<&&j+i<t.size();++j)
mm=min(mm,dis(t[i],t[i+j]));
return mm;
}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
int n;scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i].x),a[i].x+=a[i-].x,a[i].y=i;
sort(a+,a++n);
vector<int>t;
printf("%lld",dfs(,n,t));
return ;
}