# Splitting the Field (Explanation help required)

Here’s the Problem

At first it seems reasonable that this problem possibly have solution like this, but it does not even pass the sample case My Implementation
``````int n; cin >> n;
vector<array<long long, 2>> va(n);
for (int i = 0; i < n; i++) cin >> va[i] >> va[i];
sort(all(va));

vector<long long> prfs(n + 1, 0), suf(n + 1, 0);
long long a = va, b = va, c = va, d = va;
for (int i = 0; i < n; i++){
a = min(a, va[i]);
c = max(c, va[i]);
b = min(b, va[i]);
d = max(d, va[i]);
prfs[i] =  (c - a) * (d - b);
}
a = va[n - 1], b = va[n - 1], c = va[n - 1], d = va[n - 1];
for (int i = n - 1; i >= 0; --i){
a = min(a, va[i]);
c = max(c, va[i]);
b = min(b, va[i]);
d = max(d, va[i]);
suf[i] = (c - a) * (d - b);
}
long long ans = 1e18;
for (int i = 0; i < n - 1; i++){
ans = min(prfs[i] + suf[i + 1], ans);
}
cout << ans;
``````

Edit 1 : Official analysis solution of this problem is beyond my understanding yet. Could someone explain me in easy way… thank-you.

If it doesn’t pass even the sample case, then it should be pretty easy to debug on your own, no?

No, that’s not actually what I mean. There is no debug issue. I just wanna know the thought process, could you explain me the solution of this problem which is given in the official analysis.

This problem uses sweep line, basically you sort the points by x and create an imaginary vertical line that “sweeps” through the coordinate plane.

You’ll also need to use prefix sums to calculate the min/max y reached in range.