Blocked Billboard II

Solución en video

Por Jeffrey Meng

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
/**
 * @returns si (x, y) está o no en el rectángulo acotado por la esquina
 * inferior izquierda (rectBLX, rectBLY) y la esquina superior derecha (rectTRX, rectTRY)
 */
bool isInRectangle(int x, int y, int rectBLX, int rectBLY, int rectTRX, int rectTRY) {
	return (x >= rectBLX && x <= rectTRX && y >= rectBLY && y <= rectTRY);
}
 
int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);
 
	int backBLX, backBLY, backTRX, backTRY;
	cin >> backBLX >> backBLY >> backTRX >> backTRY;
	int frontBLX, frontBLY, frontTRX, frontTRY;
	cin >> frontBLX >> frontBLY >> frontTRX >> frontTRY;
 
	// Vemos cuántas esquinas están cubiertas
	int numCoveredCorners = 0;
	if (isInRectangle(backBLX, backBLY, frontBLX, frontBLY, frontTRX, frontTRY)) {
		numCoveredCorners++;
	}
	if (isInRectangle(backTRX, backBLY, frontBLX, frontBLY, frontTRX, frontTRY)) {
		numCoveredCorners++;
	}
	if (isInRectangle(backTRX, backTRY, frontBLX, frontBLY, frontTRX, frontTRY)) {
		numCoveredCorners++;
	}
	if (isInRectangle(backBLX, backTRY, frontBLX, frontBLY, frontTRX, frontTRY)) {
		numCoveredCorners++;
	}
 
	if (numCoveredCorners <= 1) {
		/*
		 * si hay 1 o 0 esquinas cubiertas, la
		 * lona es simplemente el área del rectángulo
		 */
		cout << (backTRX - backBLX) * (backTRY - backBLY) << endl;
	} else if (numCoveredCorners == 2) {
		/*
		 * si exactamente dos esquinas están cubiertas,
		 * hay que calcular el área expuesta.
		 *
		 * calculamos el área de la intersección (el área cubierta)
		 * y la restamos del área total.
		 */
		int intersectionBLX = max(backBLX, frontBLX);
		int intersectionBLY = max(backBLY, frontBLY);
		int intersectionTRX = min(backTRX, frontTRX);
		int intersectionTRY = min(backTRY, frontTRY);
		int totalAreaOfBackRectangle = (backTRX - backBLX) * (backTRY - backBLY);
		int areaOfIntersection =
		    ((intersectionTRX - intersectionBLX) * (intersectionTRY - intersectionBLY));
 
		cout << totalAreaOfBackRectangle - areaOfIntersection << endl;
	} else {
		// las 4 esquinas están cubiertas
		cout << 0 << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class Billboard {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("billboard.in"));
 
		StringTokenizer st = new StringTokenizer(in.readLine());
		int backBLX = Integer.parseInt(st.nextToken());
		int backBLY = Integer.parseInt(st.nextToken());
		int backTRX = Integer.parseInt(st.nextToken());
		int backTRY = Integer.parseInt(st.nextToken());
 
		st = new StringTokenizer(in.readLine());
		int frontBLX = Integer.parseInt(st.nextToken());
		int frontBLY = Integer.parseInt(st.nextToken());
		int frontTRX = Integer.parseInt(st.nextToken());
		int frontTRY = Integer.parseInt(st.nextToken());
 
		// Vemos cuántas esquinas están cubiertas
		int numCoveredCorners = 0;
		if (isInRectangle(backBLX, backBLY, frontBLX, frontBLY, frontTRX, frontTRY)) {
			numCoveredCorners++;
		}
		if (isInRectangle(backTRX, backBLY, frontBLX, frontBLY, frontTRX, frontTRY)) {
			numCoveredCorners++;
		}
		if (isInRectangle(backTRX, backTRY, frontBLX, frontBLY, frontTRX, frontTRY)) {
			numCoveredCorners++;
		}
		if (isInRectangle(backBLX, backTRY, frontBLX, frontBLY, frontTRX, frontTRY)) {
			numCoveredCorners++;
		}
 
		if (numCoveredCorners <= 1) {
			// si hay 1 o 0 esquinas cubiertas, la lona es el área del
			// rectángulo
			System.out.println((backTRX - backBLX) * (backTRY - backBLY));
		} else if (numCoveredCorners == 2) {
			/*
			 * si exactamente dos esquinas están cubiertas, hay que calcular el
			 * área expuesta. calculamos el área de la intersección (el área
			 * cubierta) y la restamos del área total.
			 */
			int intersectionBLX = Math.max(backBLX, frontBLX);
			int intersectionBLY = Math.max(backBLY, frontBLY);
			int intersectionTRX = Math.min(backTRX, frontTRX);
			int intersectionTRY = Math.min(backTRY, frontTRY);
			int totalAreaOfBackRectangle = (backTRX - backBLX) * (backTRY - backBLY);
			int areaOfIntersection = ((intersectionTRX - intersectionBLX) *
			                          (intersectionTRY - intersectionBLY));
 
			System.out.println(totalAreaOfBackRectangle - areaOfIntersection);
		} else {
			// las 4 esquinas están cubiertas
			System.out.println(0);
		}
	}
 
	/**
	 * @returns si (x, y) está o no en el rectángulo acotado por
	 * la esquina inferior izquierda (rectBLX, rectBLY) y
	 * la esquina superior derecha (rectTRX, rectTRY)
	 */
	public static boolean isInRectangle(int x, int y, int rectBLX, int rectBLY,
	                                    int rectTRX, int rectTRY) {
		return (x >= rectBLX && x <= rectTRX && y >= rectBLY && y <= rectTRY);
	}
}

Solución 1

Como se describe en el editorial mencionado.

Implementación

C++JavaPython


#include <cstdio>
#include <iostream>
 
using namespace std;
 
bool covered(int x, int y, int x1, int y1, int x2, int y2) {
	/*
	 * devuelve true si (x, y) está cubierto por el rectángulo acotado por
	 * (x1, y1) y (x2, y2) y false en caso contrario
	 */
	return x >= x1 && x <= x2 && y >= y1 && y <= y2;
}
 
int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);
 
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int x3, y3, x4, y4;
	cin >> x3 >> y3 >> x4 >> y4;
 
	// contamos cuántas esquinas del cartel están cubiertas
	int corner_num = 0;
	if (covered(x1, y1, x3, y3, x4, y4)) corner_num++;
	if (covered(x1, y2, x3, y3, x4, y4)) corner_num++;
	if (covered(x2, y1, x3, y3, x4, y4)) corner_num++;
	if (covered(x2, y2, x3, y3, x4, y4)) corner_num++;
 
	// si hay menos de 2 esquinas cubiertas, hay que cubrir todo el rectángulo
	if (corner_num < 2) {
		cout << (x2 - x1) * (y2 - y1);
	} else if (corner_num == 4) {
		// si las 4 esquinas están cubiertas, no hay que cubrir nada
		cout << 0;
	} else {
		// solo hay que cubrir una porción del rectángulo
		// encontramos la intersección de los dos rectángulos
		int xl = max(x1, x3);
		int xr = min(x2, x4);
		int yl = max(y1, y3);
		int yr = min(y2, y4);
		// restamos el área de la intersección
		cout << (x2 - x1) * (y2 - y1) - (xr - xl) * (yr - yl);
	}
}


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());
		int y2 = Integer.parseInt(badBoard.nextToken());
		StringTokenizer goodBoard = new StringTokenizer(read.readLine());
		int x3 = Integer.parseInt(goodBoard.nextToken());
		int y3 = Integer.parseInt(goodBoard.nextToken());
		int x4 = Integer.parseInt(goodBoard.nextToken());
		int y4 = Integer.parseInt(goodBoard.nextToken());
 
		// contamos cuántas esquinas del cartel están cubiertas
		int corner_num = 0;
		if (covered(x1, y1, x3, y3, x4, y4)) corner_num++;
		if (covered(x1, y2, x3, y3, x4, y4)) corner_num++;
		if (covered(x2, y1, x3, y3, x4, y4)) corner_num++;
		if (covered(x2, y2, x3, y3, x4, y4)) corner_num++;
 
		PrintWriter written = new PrintWriter("billboard.out");
		// si hay menos de 2 esquinas cubiertas, hay que cubrir todo el
		// rectángulo
		if (corner_num < 2) {
			written.println((x2 - x1) * (y2 - y1));
		} else if (corner_num == 4) {
			// si las 4 esquinas están cubiertas, no hay que cubrir nada
			written.println(0);
		} else {
			// solo hay que cubrir una porción del rectángulo
			// encontramos la intersección de los dos rectángulos
			int xl = Math.max(x1, x3);
			int xr = Math.min(x2, x4);
			int yl = Math.max(y1, y3);
			int yr = Math.min(y2, y4);
			// restamos el área de la intersección
			written.println((x2 - x1) * (y2 - y1) - (xr - xl) * (yr - yl));
		}
		written.close();
	}
 
	private static boolean covered(int x, int y, int x1, int y1, int x2, int y2) {
		/*
		 * devuelve true si (x, y) está cubierto por el rectángulo acotado por
		 * (x1, y1) y (x2, y2) y false en caso contrario
		 */
		return x >= x1 && x <= x2 && y >= y1 && y <= y2;
	}
}


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())
 
# qué esquinas están cubiertas por el cartel de alimento
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
 
corner_num = sum([tl_corner, tr_corner, br_corner, bl_corner])
# si estas dos esquinas están cubiertas, el cartel de la cortadora queda completamente cubierto
if bl_corner and tr_corner:
	fout.write(str(0))
 
elif corner_num in [0, 1]:
	fout.write(str(abs(x2 - x1) * abs(y2 - y1)))
 
elif br_corner and tr_corner:
	fout.write(str(abs(y2 - y1) * abs(x2 - x4)))
 
elif bl_corner and tl_corner:
	fout.write(str(abs(y2 - y1) * abs(x2 - x4)))
 
elif tr_corner and tl_corner:
	fout.write(str(abs(x2 - x1) * abs(y3 - y1)))
 
elif br_corner and bl_corner:
	fout.write(str(abs(x2 - x1) * abs(y3 - y1)))

Solución 2

Como dice el enunciado, el cartel restante de alimento para vacas está situado delante del cartel de la cortadora, y potencialmente lo oculta; por lo tanto, podemos dividirlo en seis casos a considerar.

Se usarán imágenes para visualizar los casos, así que hay que tener en cuenta lo siguiente: el color rojo muestra el área cubierta por el segundo rectángulo (cuyos bordes son negros), mientras que el verde representa el área del primer rectángulo (cuyos bordes son azules). Si dos rectángulos se intersectan, aparecerá el color rojo porque el cartel de alimento bloquea el cartel de la cortadora.

Hay que calcular el área del primer rectángulo no oculta por el segundo. Hay 6 casos a considerar, ilustrados por las imágenes de abajo:

Caso 1

En este caso, ambos rectángulos tienen las mismas coordenadas, o el primer rectángulo queda dentro del área del segundo, así que la respuesta es 0.

Caso 2

Caso 3

Caso 4

Caso 5

Caso 6

El sexto caso también incluye un caso borde en el que dos rectángulos se intersectan por las esquinas. En este caso, si la intersección de dos rectángulos está en las esquinas (las esquinas superior/inferior-izquierda/derecha de los rectángulos), hay que calcular toda el área del primer rectángulo (el rectángulo de bordes azules). La imagen de abajo ilustra el caso:

Implementación

C++JavaPython


#include <cstdio>
#include <iostream>
#include <vector>
 
 
using namespace std;
 
int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);
 
	vector<int> x(5);  // usaremos indexación desde uno
	vector<int> y(5);
	for (int i = 1; i <= 4; i++) { cin >> x[i] >> y[i]; }
 
	// Caso 1
	if (x[4] >= x[2] && x[3] <= x[1] && y[4] >= y[2] && y[3] <= y[1]) {
		cout << 0;
	}
	// Caso 2
	else if (x[3] <= x[1] && y[3] <= y[1] && y[4] > y[1] && x[4] >= x[2]) {
		cout << (x[2] - x[1]) * (y[2] - y[4]);
	}
	// Caso 3
	else if (y[3] < y[2] && x[3] <= x[1] && y[4] >= y[2] && x[4] >= x[2]) {
		cout << (x[2] - x[1]) * (y[3] - y[1]);
	}
	// Caso 4
	else if (x[4] > x[1] && x[3] <= x[1] && y[4] >= y[2] && y[3] <= y[1]) {
		cout << (x[2] - x[4]) * (y[2] - y[1]);
	}
	// Caso 5
	else if (x[3] < x[2] && x[4] >= x[2] && y[4] >= y[2] && y[3] <= x[1]) {
		cout << (x[3] - x[1]) * (y[2] - y[1]);
	}
	// Caso 6 y el caso borde
	else {
		cout << (x[2] - x[1]) * (y[2] - y[1]);
	}
}


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"));
		// usaremos indexación desde uno para que quede más claro
		int[] x = new int[4 + 1];
		int[] y = new int[4 + 1];
		for (int i = 1; i <= 4; i++) {
			x[i] = scanner.nextInt();
			y[i] = scanner.nextInt();
		}
 
		PrintWriter written = new PrintWriter("billboard.out");
		// Caso 1
		if (x[4] >= x[2] && x[3] <= x[1] && y[4] >= y[2] && y[3] <= y[1]) {
			written.println(0);
		}
		// Caso 2
		else if (x[3] <= x[1] && y[3] <= y[1] && y[4] > y[1] && x[4] >= x[2]) {
			written.println((x[2] - x[1]) * (y[2] - y[4]));
		}
		// Caso 3
		else if (y[3] < y[2] && x[3] <= x[1] && y[4] >= y[2] && x[4] >= x[2]) {
			written.println((x[2] - x[1]) * (y[3] - y[1]));
		}
		// Caso 4
		else if (x[4] > x[1] && x[3] <= x[1] && y[4] >= y[2] && y[3] <= y[1]) {
			written.println((x[2] - x[4]) * (y[2] - y[1]));
		}
		// Caso 5
		else if (x[3] < x[2] && x[4] >= x[2] && y[4] >= y[2] && y[3] <= x[1]) {
			written.println((x[3] - x[1]) * (y[2] - y[1]));
		}
		// Caso 6 y el caso borde
		else {
			written.println((x[2] - x[1]) * (y[2] - y[1]));
		}
		written.close();
	}
}


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())
 
# usaremos indexación desde uno para que quede más claro
x = [0, x1, x2, x3, x4]
y = [0, y1, y2, y3, y4]
 
# Caso 1
if x[4] >= x[2] and x[3] <= x[1] and y[4] >= y[2] and y[3] <= y[1]:
	fout.write(str(0))
# Caso 2
elif x[3] <= x[1] and y[3] <= y[1] and y[4] > y[1] and x[4] >= x[2]:
	fout.write(str((x[2] - x[1]) * (y[2] - y[4])))
# Caso 3
elif y[3] < y[2] and x[3] <= x[1] and y[4] >= y[2] and x[4] >= x[2]:
	fout.write(str((x[2] - x[1]) * (y[3] - y[1])))
# Caso 4
elif x[4] > x[1] and x[3] <= x[1] and y[4] >= y[2] and y[3] <= y[1]:
	fout.write(str((x[2] - x[4]) * (y[2] - y[1])))
# Caso 5
elif x[3] < x[2] and x[4] >= x[2] and y[4] >= y[2] and y[3] <= x[1]:
	fout.write(str((x[3] - x[1]) * (y[2] - y[1])))
# Caso 6 y el caso borde
else:
	fout.write(str((x[2] - x[1]) * (y[2] - y[1])))