USACO 2016 US Open Contest Silver Division - Field Reduction

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Unlike the bronze version, here we can remove up to three cows to make the area as small as possible.

A strategy which makes a lot of sense given this detail is that we want to remove cows which are placed near the extremes (top, left, right, bottom). Since there can be many such cows, we can fix the boundaries of our rectangle and try them all, with the goal of finding one such bounding box that has at most three cows outside of it.

The smallest such bounding box will therefore be our answer.

Source code

The source code in C++ can be seen below.

#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

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

    int n;
    cin >> n;

    vector<pair<int, int> > vp(n + 1);
    vector<int> ox(n + 1), oy(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> vp[i].first >> vp[i].second;
        ox[i] = vp[i].first;
        oy[i] = vp[i].second;
    }

    sort(ox.begin() + 1, ox.begin() + n + 1);
    sort(oy.begin() + 1, oy.begin() + n + 1);

    int ans = (ox[n] - ox[1]) * (oy[n] - oy[1]);
    for (int pxmin = 1; pxmin <= 4; pxmin++) {
        for (int pxmax = max(pxmin, n - 3); pxmax <= n; pxmax++) {
            for (int pymin = 1; pymin <= 4; pymin++) {
                for (int pymax = max(pymin, n - 3); pymax <= n; pymax++) {
                    int cnt = 0;
                    for (int i = 1; i <= n; i++) {
                        if (vp[i].first >= ox[pxmin] && vp[i].first <= ox[pxmax] && vp[i].second >= oy[pymin] &&
                            vp[i].second <= oy[pymax]) {
                            cnt++;
                        }
                    }
                    if (cnt >= n - 3) {
                        ans = min(ans, (ox[pxmax] - ox[pxmin]) * (oy[pymax] - oy[pymin])); 
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}