Free Bronze Problems / Marathon

Resources & Problemsets
#1

If anyone wants some arbitrary bronze problems (especially if you’re still starting out), I’ll let this be a thread to post them. If you want to propose your own problems, you can make this a marathon as well, but for now I have at least two problems I will post here. In any case, please post original problems instead of already existing USACO problems.

Here’s the first (below). If you solve it, feel free to post your solution! Include hide tags so others can try :slight_smile:

Once someone successfully solves this, I will post the second problem.

Grazing Patterns

Farmer John is constructing a new grass field. Each of his N cows, conveniently numbered 1 \dots N, has a favorite grazing pattern, and the accommodating farmer he is, Farmer John wants to ensure the new field remains large enough for all cows to graze without having to exit the field.

Formally, if the grass field is a perfect axis-aligned rectangle (horizontal sides parallel to the x axis and vertical sides parallel to the y axis), the favorite grazing pattern of cow i starts at some point (x_i, y_i), travels horizontally h_i units (rightward for positive h_i, leftward for negative h_i, and nowhere for h_i=0) to the point (x_i + h_i, y_i), and finally travels vertically v_i units (upward for positive v_i, downward for negative v_i, and nowhere for v_i=0) to the point (x_i + h_i, y_i + v_i).

For instance, the grazing pattern of a cow starting at (3,4) traveling horizontally -4 and vertically 2 would take her left from (3,4) to (-1,4) and up from (-1,4) to (-1,6).

It is possible for the grazing patterns of two cows to cross – assume that they travel around each other without deviating significantly from their paths. The new field does not have to be in the first quadrant – it can be anywhere in the coordinate plane as long as it remains axis-aligned and satisfies the constraints.

Given the grazing patterns of all N cows, find the minimum horizontal and vertical dimensions allowable for Farmer John’s new field.

INPUT FORMAT (graze.in):

The first line of input contains the value of N. It is guaranteed that 1 \leq N \leq 10^5.

The next N lines of input are as follows:

For all cows i = 1 \dots N, line i+1 contains the space-separated integers x_i, y_i, h_i, v_i describing the favorite grazing pattern of cow i. It is guaranteed that -10^5 \leq x_i, y_i, h_i, v_i \leq 10^5.

OUTPUT FORMAT (graze.out):

Output one line containing two space-separated integers describing the answer, first the minimum horizontal dimension and second the minimum vertical dimension.

SAMPLE INPUT:

2
3 4 -4 2
0 0 4 4

SAMPLE OUTPUT:

5 6

The field can have bottom left corner (-1,0) and top right corner (4,6).

2 Likes
#2

Thanks! I’ve moved this to the Resources and Problemsets category and pinned it.

2 Likes
#3
#4

Nice initiative!

Hoping for something similar for the Silver/Gold Division as well

#5

Thank you, I’ll try to do this problem.

#6

Here is my C++ code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for(ll i=a; i<b; ++i)

void setIO(string name="") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); 
    if((ll)name.size() > 0){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int main(){
	setIO("graze");
	ll minX = 100000, minY = 100000;
	ll maxX = -100000, maxY = -100000; 
	ll n; cin >> n;
	FOR(i, 0, n){
		ll x, y, h, v; cin >> x >> y >> h >> v;
		minX = min(x, minX); minX = min(x+h, minX);
		minY = min(y, minY); minY = min(y+v, minY);
		maxX = max(x, maxX); maxX = max(x+h, maxX);
		maxY = max(y, maxY); maxY = max(y+v, maxY);
	}
	cout << maxX - minX << " " << maxY - minY << endl;
}

LOL I did this in like 10 minutes, so I’m probably wrong.

#7

Just look up the problem and submit it on USACO to see if ur right

#8

Huh? I think the user @passionunlimited made this problem. I don’t think I can submit on USACO.

#9

You sure long longs are needed? I think just normal ints should be able to handle the numbers in this problem. (also macros ew)

#10

Doesn’t matter…