Codeforces Round #245 (Div. 1)??Tricky Function_html/css_WEB-ITnose

Question link

Question meaning:
n numbers a[i], f(i, j) = (i - j) ^ 2 sigma( a[k]) ^ 2, i < k <= j, find the minimum f value
n (2?≤?n?≤?100000).(?-?104?≤?a[i] ?≤?104)

Analysis:
The key lies in the conversion of the meaning of the question. Simply consider, you need to know the information of each interval, and the complexity is difficult to reduce. The f function of the question should be simplified. Since it is not feasible to consider the interval, try to calculate whether the interval can be divided into two short points. A common conversion is used here: the interval sum is converted into the difference of the prefix sum. After conversion, we get f(i, j) = (i - j) ^ 2 (presum[j] - presum[i]) ^ 2. Anyone who has done geometry can see that it is the nearest point pair on the plane

Summary:
If the interval is used as the unit of the problem, then the complexity is difficult to reduce, so the unit of consideration for the problem is often points. If it can be converted into points, the complexity will be reduced
The sum of intervals often needs to be converted into Prefix sum: In this case, for two points in the interval, the value to be calculated is only related to the current point, that is, the previous task (converting the interval into points) is completed

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;}