Stuck on the problem Blocked Billboard II under the Rectangle Geometry section of the guide.
In an attempt to try to solve the problem I came up with four possible test cases that could be solved after calculating the x and y overlaps between the two rectangles. Here is the function I am using to calculate the intersection lengths:
struct Rect {
int x1,y1,x2,y2;
int area() {return (x2-x1)*(y2-y1);}
int x_len() {return x2-x1;}
int y_len() {return y2-y1;}
};
int y_overlap(Rect p, Rect q) {
return max(min(p.y2,q.y2)-max(p.y1,q.y1),0);
}
int x_overlap(Rect p, Rect q) {
return max(min(p.x2,q.x2)-max(p.x1,q.x1),0);
}
Using the x and y overlaps I distinguish between test cases.
-
The first test case: the cow feed billboard completely covers the lawnmower billboard, in which case the x and y overlap values will be greater than the x\_len() and y\_len() values for the lawnmower billboard.
-
The second test case: the cow feed billboard is smaller in area than the lawnmower billboard, or is only obscuring one corner, in which case we will need to cover the whole lawnmower billboard. Here the x and y overlaps are both smaller than x\_len() and y\_len() (of the lawnmower billboard).
-
The third test case: the cow feed billboard’s x overlap is greater than or equal to the lawnmower’s x\_len(), this would only require me to calculate the difference between the y overlap and the lawnmower billboard’s y\_len(), the difference multiplied with x\_len() will give the area to be covered on the lawnmower billboard.
-
The fourth test case: similar to the last test case this time the cow feed billboard’s y overlap is greater than or equal to the lawnmower’s, but the x overlap is not.
Here is my code implementing the four test cases above:
void setIO(string name = "") {
FAST;
if(sz(name)) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
struct Rect {
int x1,y1,x2,y2;
int area() {return (x2-x1)*(y2-y1);}
int x_len() {return x2-x1;}
int y_len() {return y2-y1;}
};
int y_overlap(Rect p, Rect q) {
return max(min(p.y2,q.y2)-max(p.y1,q.y1),0);
}
int x_overlap(Rect p, Rect q) {
return max(min(p.x2,q.x2)-max(p.x1,q.x1),0);
}
void solve() {
Rect a,b;
cin >> a.x1 >> a.y1 >> a.x2 >> a.y2;
cin >> b.x1 >> b.y1 >> b.x2 >> b.y2;
int ans;
int xo = x_overlap(a,b), yo = y_overlap(a,b);
if(xo>=a.x_len() && yo>=b.y_len()) {
ans = 0;
} else if(xo<a.x_len() && yo<a.y_len()) {
ans = a.area();
} else if(xo>=a.x_len() && yo<a.y_len()) {
ans = a.x_len()*(a.y_len()-yo);
} else if(yo>=a.y_len() && xo<a.x_len()) {
ans = a.y_len()*(a.x_len()-xo);
}
cout << ans;
}
int main() {
setIO("billboard");
solve();
}
What I don’t seem to understand is which test case this solution approach might not be covering. The USACO grader fails on one particular test case (all the other ones seem to pass). Should I be changing how I approach this problem, something like in the Official Analysis, or look at it from a different perspective?
Any help is appreciated.
Thanks!
