USACO Bronze 2018 January - Blocked Billboard II

Authors: Melody Yu, Danh Ta Chi Thanh, Jeffrey Meng

Edit This Page

Official Analysis

Video Solution

By Jeffrey Meng

Video Solution Code

Solution 1

As described in the aforementioned editorial.

Implementation

C++

#include <cstdio>
#include <iostream>


using namespace std;


bool covered(int x, int y, int x1, int y1, int x2, int y2) {
	/*
	 * returns true if (x, y) is covered by the rectangle bounded by
	 * (x1, y1) and (x2, y2) and false otherwise
	 */

Java

import java.io.*;
import java.util.StringTokenizer;


public class Billboard {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("billboard.in"));
		StringTokenizer badBoard = new StringTokenizer(read.readLine());
		int x1 = Integer.parseInt(badBoard.nextToken());
		int y1 = Integer.parseInt(badBoard.nextToken());
		int x2 = Integer.parseInt(badBoard.nextToken());

Python

fin, fout = open("billboard.in"), open("billboard.out", "w")


x1, y1, x2, y2 = map(int, fin.readline().split())
x3, y3, x4, y4 = map(int, fin.readline().split())


# which corners are covered by the feed billboard
tl_corner = x3 <= x1 and y4 >= y2
tr_corner = y4 >= y2 and x4 >= x2
br_corner = x4 >= x2 and y3 <= y1
bl_corner = y3 <= y1 and x3 <= x1

Solution 2

As the problem statement says, the remaining cow feed billboard is situated in front of the lawnmower billboard, potentially obscuring it; therefore, we can split it into six cases to consider.

Images will be used to visualize the cases, so note these things: The red color shows the area covered by the second rectangle (whose borders are black), while the green one represents the area of the first rectangle (whose edges are blue). If two rectangles intersect, the red color will appear as the cow feed billboard block the lawnmower billboard.

We have to calculate the area of the first rectangle not obscured by the second one. There are 6 cases to consider, illustrated by the images below:

Case 1

In this case, both rectangles have the same coordinates, or the first rectangle lies in the area of the second one, so the answer is 0.

Case 1 1

Case 1 2

Case 2

Case 2

Case 3

Case 3

Case 4

Case 4

Case 5

Case 5

Case 6

Case 6

The sixth case also includes a corner case where two rectangles intersect with their corners. In this case, if the intersection of two rectangles is at the corners (the top/down-left/right corners of the rectangles), we have to calculate the entire area of the first rectangle (the blue-edged rectangle). The image below illustrates the case:

Corner Case

Implementation

C++

#include <cstdio>
#include <iostream>
#include <vector>


using namespace std;


int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);

Java

import java.io.*;
import java.util.Scanner;


public class Billboard {
	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(new FileReader("billboard.in"));
		// we'll be using 1-indexing to make things more obvious
		int[] x = new int[4 + 1];
		int[] y = new int[4 + 1];
		for (int i = 1; i <= 4; i++) {

Python

fin, fout = open("billboard.in"), open("billboard.out", "w")


x1, y1, x2, y2 = map(int, fin.readline().split())
x3, y3, x4, y4 = map(int, fin.readline().split())


# we'll be using one-indexing to make things more obvious
x = [0, x1, x2, x3, x4]
y = [0, y1, y2, y3, y4]


# Case 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum