题目链接：http://codeforces.com/problemset/problem/429/D
题目大意：
给定一个长度为 \(n\) 的数列 \(a_1, a_2, \ldots, a_n\)。
用 \(s\) 表示 \(a\) 的前缀和数组，即 \(s_i = \sum\limits_{j = 1}^i a_j\)
定义 \(f(i, j) = (i - j)^2 + (s_i - s_j)^2\)
求所有 \(i \neq j\) 的 \(f(i, j)\) 的最小值。
解题思路：
将 \(i\) 作为横坐标，\(s_i\) 作为纵坐标，\((i - j)^2 + (s_i - s_j)^2\) 作为两点之间距离。求平面最近点对。
示例程序（在平面最近点对代码上稍作了一点修改）：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct Node {
long long x, y;
} a[maxn], b[maxn];
bool cmp_x(Node a, Node b) {
return a.x < b.x;
}
bool cmp_y(Node a, Node b) {
return a.y < b.y;
}
long long dis(Node a, Node b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int n;
long long A[maxn];
long long solve(int l, int r) {
if (l >= r) return 2e9;
int mid = (l + r) / 2;
long long d = min(solve(l, mid), solve(mid+1, r));
int p = 0;
for (int i = l; i <= r; i++) if ((a[i].x - a[mid].x) * (a[i].x - a[mid].x) < d) b[p++] = a[i];
sort(b, b+p, cmp_y);
for (int i = 0; i < p; i++)
for (int j = i+1; j < p && (b[j].y - b[i].y) * (b[j].y - b[i].y) < d; j++)
d = min(d, dis(b[i], b[j]));
return d;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", A+i);
A[i] += A[i-1];
a[i].x = i;
a[i].y = A[i];
}
sort(a+1, a+n+1, cmp_x);
printf("%lld\n", solve(1, n));
return 0;
}