USACO 2016 US Open Contest Bronze Division - Field Reduction

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can solve this by adding all coordinates in a multiset and when we remove one coordinate, we find the smallest and the greatest \(x\) and \(y\) coordinate in order to find the area of the rectangle in question.

In order to perform these things easily, you can rely on the lower bound and upper bound methods from the set data structure which allow us to keep track of the minimums and maximums easily.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int n, vx[50001], vy[50001];

int main()
{
    ifstream cin("reduce.in");
    ofstream cout("reduce.out");

    multiset<int> x, y;

    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> vx[i] >> vy[i];
        x.insert(vx[i]);
        y.insert(vy[i]);
    }

    int ans = 2000000001;

    for(int i = 1; i <= n; i++)
    {
        x.erase(x.lower_bound(vx[i]));
        y.erase(y.lower_bound(vy[i]));

        int minx = *x.begin();
        int miny = *y.begin();
        int maxx = *x.rbegin();
        int maxy = *y.rbegin();

        ans = min(ans, (maxy-miny) * (maxx-minx));

        x.insert(vx[i]);
        y.insert(vy[i]);
    }

    cout << ans;
    return 0;
}

with open("diamond.in", "r") as fin:
    data = fin.read().split()
n = int(data[0])
k = int(data[1])
v = [0] + list(map(int, data[2:2+n]))
v[1:] = sorted(v[1:])

ans = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        if v[j] - v[i] <= k:
            ans = max(ans, j - i + 1)

with open("diamond.out", "w") as fout:
    fout.write(str(ans))