时间：2021-07-01 10:21:17 帮助过：3人阅读
const double EPS = 1e-10;const int MAXN = 100100;inline int dcmp(double x){ if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1;}struct Point{ LL x, y;};//最近点对Point point[MAXN];LL tmpt[MAXN], Y[MAXN];inline bool cmpxy(Point a, Point b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y;}inline bool cmpy(int a, int b){ return point[a].y < point[b].y;}inline LL dist(int x, int y){ Point& a = point[x], &b = point[y]; return sqr(a.x - b.x) + sqr(a.y - b.y);}LL Closest_Pair(int left, int right){ LL d = 1e18; if(left == right) return d; if(left + 1 == right) return dist(left, right); int mid = (left + right) >> 1; double d1 = Closest_Pair(left, mid); double d2 = Closest_Pair(mid + 1, right); d = min(d1, d2); int k = 0; //分离出宽度为d的区间 FE(i, left, right) { if(sqr(point[mid].x - point[i].x) <= d) tmpt[k++] = i; } sort(tmpt, tmpt + k, cmpy); //线性扫描 REP(i, k) for(int j = i + 1; j < k && sqr(point[tmpt[j]].y-point[tmpt[i]].y) < d; j++) { LL d3 = dist(tmpt[i],tmpt[j]); if(d > d3) d = d3; } return d;}LL ipt[MAXN];int main(){ //freopen("input.txt", "r", stdin); int n; while (~RI(n) && n) { FE(i, 1, n) { cin >> ipt[i]; ipt[i] = ipt[i - 1] + ipt[i]; } FE(i, 1, n) { point[i - 1].x = i; point[i - 1].y = ipt[i]; } sort(point, point + n, cmpxy); LL ans = Closest_Pair(0, n - 1); cout << ans << endl; } return 0;}