题意：给定一个数组你个数的数组a，定义sum(i, j)表示sigma(a[i],...a[j]),以及另外一个函数f(i, j) = (i - j)^2 + sum(i+1, j)^2
求最小的f(i, j)(i < j)
思路：变形一下f(i, j) = (i - j)^2 + (sum[j] - sum[i])^2
那么把i看成x，sum[i]看成y，那就等价于求二维平面的最近点对吗。
二维平面求最近点对有一个经典nlognlogn的分治算法。。
code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second
const int Inf = 0x3fffffff;
pair<int, int> p[], tmp[];
int n;
ll dis(int x, int y, int x1, int y1){
ll dx = x - x1, dy = y - y1;
return dx * dx + dy * dy;
} bool cmp(const pii& a, const pii& b){
return a.y < b.y;
} ll X, Y, k;
ll solve(const int l,const int r){
if (l == r) return Inf;
int m = (l + r) >> ;
ll d = solve(l, m), d1 = solve(m+, r);
d = min(d, d1);
k = ;
X = p[m].x;
for (int i = l; i <= r; ++i)
if ((X-p[i].x) * (X-p[i].x) <= d) tmp[k++] = p[i];
sort(tmp, tmp + k, cmp);
for (int i = ; i < k; ++i){
Y = tmp[i].y;
for (int j = i+; j < k; ++j){
if ((Y - tmp[j].y) * (Y - tmp[j].y) > d) break;
d = min(d, dis(tmp[i].x, tmp[i].y, tmp[j].x, tmp[j].y));
}
}
return d;
} void solve(){
p[] = make_pair(, );
int u;
for (int i = ; i <= n; ++i)
scanf("%d", &u), p[i].x = i, p[i].y = p[i-].y + u;
ll ans = solve(, n);
cout << ans << endl;
} int main(){
// freopen("a.in", "r", stdin);
while (scanf("%d", &n) != EOF){
solve();
}
}