Geometría de rectángulos

Recursos
Fuente	Recurso	Notas
IUSACO	7.1 - Rectangle Geometry	el módulo se basa en esto

La mayoría de los problemas de esta categoría incluyen solo dos o tres cuadrados o rectángulos, en cuyo caso se pueden dibujar los casos en papel. Eso debería llevar de forma lógica a una solución.

Ejemplo - Fence Painting

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Bronze	Fence Painting	Fácil	Rectangle	Solución

Solución lenta

Como todos los intervalos están en el rango $[0, 100]$ , podemos marcar cada intervalo de longitud $1$ contenido dentro de cada intervalo como pintado usando un bucle. Luego la respuesta será la cantidad de intervalos marcados.

Figura · unión de intervalos

Clic para el inicio de FJ. Cada listón es un metro [i, i+1).

(10−7) + (8−4) − 1 = 6 metros pintados

Complejidad temporal: $\mathcal{O}(\text{max coordinate})$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_POS = 100;
 
int main() {
	freopen("paint.in", "r", stdin);
	freopen("paint.out", "w", stdout);
 
	int a, b, c, d;
	cin >> a >> b >> c >> d;
 
	vector<bool> painted(MAX_POS + 1);
	// Agregar el intervalo pintado de Farmer John
	for (int i = a; i < b; i++) { painted[i] = true; }
	// Agregar el intervalo pintado de Bessie
	for (int i = c; i < d; i++) { painted[i] = true; }
 
	// Contar la cantidad total de intervalos pintados
	int total = 0;
	for (bool i : painted) { total += i; }
 
	cout << total << endl;
}


import java.io.*;
import java.util.*;
 
public class Paint {
	static final int MAX_POS = 100;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("paint");
		int a = io.nextInt();
		int b = io.nextInt();
		int c = io.nextInt();
		int d = io.nextInt();
 
		boolean[] painted = new boolean[MAX_POS + 1];
		// Agregar el intervalo pintado de Farmer John
		for (int i = a; i < b; i++) { painted[i] = true; }
		// Agregar el intervalo pintado de Bessie
		for (int i = c; i < d; i++) { painted[i] = true; }
 
		// Contar la cantidad total de intervalos pintados
		int total = 0;
		for (boolean i : painted) { total += i ? 1 : 0; }
 
		io.println(total);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import sys
 
MAX_POS = 100
 
sys.stdin = open("paint.in", "r")
sys.stdout = open("paint.out", "w")
 
a, b = map(int, input().split())
c, d = map(int, input().split())
 
painted = [False for _ in range(MAX_POS + 1)]
# Agregar el intervalo pintado de Farmer John
for i in range(a, b):
	painted[i] = True
# Agregar el intervalo pintado de Bessie
for i in range(c, d):
	painted[i] = True
 
print(sum(painted))  # Imprimir la cantidad total de intervalos pintados

Sin embargo, esta solución no funcionaría con restricciones más altas (por ejemplo, si las coordenadas llegaran hasta $10^9$ ).

Solución rápida

Calculamos la respuesta sumando las longitudes originales y restando la longitud de la intersección.

(b-a)+(d-c)-\text{intersection}([a,b],[c,d])

El análisis oficial divide el cálculo de la longitud de la intersección en varios casos. Sin embargo, podemos hacerlo de forma más simple. Un intervalo $[x,x+1]$ está contenido tanto en $[a,b]$ como en $[c,d]$ si $a\le x$ , $c\le x$ , $x<b$ y $x<d$ , o, en otras palabras, si $\max(a,c)\le x$ y $x<\min(b,d)$ . Así, la longitud de la intersección es $\min(b,d)-\max(a,c)$ si esta cantidad es positiva y cero en caso contrario.

Complejidad temporal: $\mathcal{O}(1)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("paint.in", "r", stdin);
	freopen("paint.out", "w", stdout);
 
	int a, b, c, d;
	cin >> a >> b >> c >> d;
 
	int total = (b - a) + (d - c);                     // la suma de los dos intervalos
	int intersection = max(min(b, d) - max(a, c), 0);  // restar la intersección
	int ans = total - intersection;
 
	cout << ans << "\n";
}


import java.io.*;
import java.util.*;
 
public class Paint {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("paint");
		int a = io.nextInt();
		int b = io.nextInt();
		int c = io.nextInt();
		int d = io.nextInt();
 
		// la suma de los dos intervalos
		int total = (b - a) + (d - c);
		// restar la intersección
		int intersection = Math.max(Math.min(b, d) - Math.max(a, c), 0);
		int union = total - intersection;
 
		io.println(union);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import sys
 
sys.stdin = open("paint.in", "r")
sys.stdout = open("paint.out", "w")
 
a, b = map(int, input().split())
c, d = map(int, input().split())
total = (b - a) + (d - c)  # la suma de los dos intervalos
intersection = max(min(b, d) - max(a, c), 0)  # restar la intersección
union = total - intersection
 
print(union)

Ejemplo - Blocked Billboard

Pensalo como el análogo en 2D del ejemplo anterior.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Bronze	Blocked Billboard	Normal	Rectangle	en el módulo

Solución lenta

Complejidad temporal: $\mathcal{O}((\text{max coordinate})^2)$

Como todas las coordenadas están en el rango $[-1000,1000]$ , podemos recorrer cada uno de los $2000^2$ cuadrados visibles posibles y comprobar cuáles son visibles con bucles anidados.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_POS = 2000;
bool visible[MAX_POS][MAX_POS];
 
int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);
	for (int i = 0; i < 3; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		// hacer positivas todas las coordenadas
		x1 += MAX_POS / 2;
		y1 += MAX_POS / 2;
		x2 += MAX_POS / 2;
		y2 += MAX_POS / 2;
		for (int x = x1; x < x2; x++) {
			// Marcar el área del cartel como visible y la del camión como no visible
			for (int y = y1; y < y2; y++) { visible[x][y] = i < 2; }
		}
	}
 
	// Contar todos los cuadrados visibles de los carteles
	int ans = 0;
	for (int x = 0; x < MAX_POS; x++) {
		for (int y = 0; y < MAX_POS; y++) { ans += visible[x][y]; }
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class Billboard {
	private static final int MAX_POS = 2000;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("billboard");
		int visible[][] = new int[MAX_POS][MAX_POS];
 
		for (int i = 0; i < 3; ++i) {
			int x1 = io.nextInt();
			int y1 = io.nextInt();
			int x2 = io.nextInt();
			int y2 = io.nextInt();
			// hacer positivas todas las coordenadas
			x1 += MAX_POS / 2;
			y1 += MAX_POS / 2;
			x2 += MAX_POS / 2;
			y2 += MAX_POS / 2;
			// Marcar el área del cartel como visible y la del camión como no visible
			for (int x = x1; x < x2; x++) {
				for (int y = y1; y < y2; y++) { visible[x][y] = i < 2 ? 1 : 0; }
			}
		}
 
		// Contar todos los cuadrados visibles de los carteles
		int ans = 0;
		for (int x = 0; x < 2000; ++x) {
			for (int y = 0; y < 2000; ++y) { ans += visible[x][y]; }
		}
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

El código en Python corre un poco más rápido cuando está dentro de una función , así que podemos usar esto para pasar los 10 casos de prueba. Si se saca de la función, el código solo pasa 9 casos.


import sys
 
MAX_POS = 2000
 
 
def main():
	sys.stdin = open("billboard.in", "r")
	sys.stdout = open("billboard.out", "w")
 
	visible = [[False for _ in range(MAX_POS)] for _ in range(MAX_POS)]
 
	for i in range(3):
		x1, y1, x2, y2 = map(int, input().split())
		x1 += MAX_POS // 2
		y1 += MAX_POS // 2
		x2 += MAX_POS // 2
		y2 += MAX_POS // 2
		# Marcar el área del cartel como visible y la del camión como no visible
		for x in range(x1, x2):
			for y in range(y1, y2):
				visible[x][y] = i < 2
 
	# Contar todos los cuadrados visibles de los carteles
	ans = 0
	for x in range(MAX_POS):
		for y in range(MAX_POS):
			ans += visible[x][y]
	print(ans)
 
 
main()

Esto no alcanzaría si las coordenadas llegaran hasta $10^9$ .

Solución rápida

Complejidad temporal: $\mathcal{O}(1)$

Análisis oficial

JavaC++Python

Crear una clase Rect para representar un rectángulo hace que el código sea más fácil de entender.


import java.io.*;
import java.util.*;
 
class Rect {
	int x1, y1, x2, y2;
	int area() { return (y2 - y1) * (x2 - x1); }  // Área del rectángulo
}
 
public class Billboard {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("billboard");
 
		Rect a = new Rect(), b = new Rect(), t = new Rect();
		a.x1 = io.nextInt();
		a.y1 = io.nextInt();
		a.x2 = io.nextInt();
		a.y2 = io.nextInt();
		b.x1 = io.nextInt();
		b.y1 = io.nextInt();
		b.x2 = io.nextInt();
		b.y2 = io.nextInt();
		t.x1 = io.nextInt();
		t.y1 = io.nextInt();
		t.x2 = io.nextInt();
		t.y2 = io.nextInt();
 
		// Área visible total = área de ambos carteles menos el área cubierta por el camión
		io.println(a.area() + b.area() - intersect(a, t) - intersect(b, t));
		io.close();
	}
 
	static int intersect(Rect p, Rect q) {
		// Calcular la superposición en las direcciones x e y
		int xOverlap = Math.max(0, Math.min(p.x2, q.x2) - Math.max(p.x1, q.x1));
		int yOverlap = Math.max(0, Math.min(p.y2, q.y2) - Math.max(p.y1, q.y1));
		return xOverlap * yOverlap;  // Área de la intersección
	}
 
	// CodeSnip{Kattio}
}

Implementación alternativa

También podemos usar la clase integrada Rectangle. Para crear un rectángulo nuevo, usamos el siguiente constructor:


/*
 * Crea un rectángulo con esquina superior izquierda en (x,y)
 * con un ancho y una altura dados.
 */
Rectangle newRect = new Rectangle(x, y, width, height);

La clase Rectangle soporta numerosos métodos útiles, entre ellos los siguientes:

firstRect.intersects(secondRect) comprueba si dos rectángulos se intersectan.
firstRect.union(secondRect) devuelve un rectángulo que representa la unión de dos rectángulos.
firstRect.contains(x, y) comprueba si el punto entero $(x,y)$ está en firstRect.
firstRect.intersection(secondRect) devuelve un rectángulo que representa la intersección de dos rectángulos.
rect.isEmpty() comprueba si rect está vacío.

Esta clase a menudo reduce la implementación necesaria en algunos problemas de Bronce y de Codeforces.

Con la clase integrada Rectangle:


import java.awt.Rectangle;
import java.io.*;
import java.util.*;
 
public class Billboard {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("billboard");
 
		int x1, y1, x2, y2;
		x1 = io.nextInt();
		y1 = io.nextInt();
		x2 = io.nextInt();
		y2 = io.nextInt();
		Rectangle firstRect = new Rectangle(x1, -y2, x2 - x1, y2 - y1);
 
		x1 = io.nextInt();
		y1 = io.nextInt();
		x2 = io.nextInt();
		y2 = io.nextInt();
		Rectangle secondRect = new Rectangle(x1, -y2, x2 - x1, y2 - y1);
 
		x1 = io.nextInt();
		y1 = io.nextInt();
		x2 = io.nextInt();
		y2 = io.nextInt();
		Rectangle truck = new Rectangle(x1, -y2, x2 - x1, y2 - y1);
 
		long firstIntersect = getArea(firstRect.intersection(truck));
		long secondIntersect = getArea(secondRect.intersection(truck));
 
		io.println(getArea(firstRect) + getArea(secondRect) - firstIntersect -
		           secondIntersect);
		io.close();
	}
 
	public static long getArea(Rectangle r) {
		return r.isEmpty() ? 0 : (long)r.getHeight() * (long)r.getWidth();
	}
 
	// CodeSnip{Kattio}
}

Opcional

java.awt.geom.Area permite calcular la unión, la intersección, la diferencia o el o exclusivo de polígonos arbitrarios (y más). Ver aquí un ejemplo de uso.

Nótese que crear un struct Rect para representar un rectángulo hace que el código sea más fácil de entender.


#include <bits/stdc++.h>
using namespace std;
 
struct Rect {
	int x1, y1, x2, y2;
	void read() { cin >> x1 >> y1 >> x2 >> y2; }
	int area() { return (y2 - y1) * (x2 - x1); }  // Área del rectángulo
};
 
int intersect(Rect p, Rect q) {
	// Calcular la superposición en las direcciones x e y
	int xOverlap = max(0, min(p.x2, q.x2) - max(p.x1, q.x1));
	int yOverlap = max(0, min(p.y2, q.y2) - max(p.y1, q.y1));
	return xOverlap * yOverlap;  // Área de la intersección
}
 
int main() {
	freopen("billboard.in", "r", stdin);
	freopen("billboard.out", "w", stdout);
 
	Rect a, b, t;  // carteles a, b, y el camión
	a.read();
	b.read();
	t.read();
 
	// Área visible total = área de ambos carteles menos el área cubierta por el camión
	cout << a.area() + b.area() - intersect(a, t) - intersect(b, t) << endl;
}

Nótese que crear una clase Rect para representar un rectángulo hace que el código sea más fácil de entender.


import sys
 
 
class Rect:
	def __init__(self):
		# Leer las coordenadas del rectángulo desde la entrada
		self.x1, self.y1, self.x2, self.y2 = map(int, input().split())
 
	def area(self):
		# Calcular el área del rectángulo
		return (self.y2 - self.y1) * (self.x2 - self.x1)
 
 
def intersect(p, q):
	# Calcular la superposición en la dirección x
	x_overlap = max(0, min(p.x2, q.x2) - max(p.x1, q.x1))
	# Calcular la superposición en la dirección y
	y_overlap = max(0, min(p.y2, q.y2) - max(p.y1, q.y1))
	return x_overlap * y_overlap  # Área de la intersección
 
 
sys.stdin = open("billboard.in", "r")
sys.stdout = open("billboard.out", "w")
 
rects = []
for _ in range(3):
	rects.append(Rect())  # Leer los dos carteles y el camión
 
print(
	rects[0].area()  # Área del primer cartel
	+ rects[1].area()  # Área del segundo cartel
	- intersect(rects[0], rects[2])  # Restar el área del primer cartel cubierta por el camión
	- intersect(
		rects[1], rects[2]
	)  # Restar el área del segundo cartel cubierta por el camión
)

Fórmulas comunes

Ciertas tareas aparecen a menudo en problemas de geometría de rectángulos. Por ejemplo, muchos problemas piden el área de superposición de dos o más rectángulos a partir de sus puntos de coordenadas, o determinar si dos rectángulos se intersectan. Acá discutimos esas fórmulas.

Nótese que estas fórmulas solo aplican a rectángulos con lados paralelos a los ejes de coordenadas.

Calcular el área

La fórmula del área de un rectángulo individual es $w \cdot l$ .

$\texttt{length}$ es la longitud de los lados verticales, y $\texttt{width}$ es la longitud de los lados horizontales.

$\texttt{width} = \texttt{tr}_x - \texttt{bl}_x$
$\texttt{length} = \texttt{tr}_y - \texttt{bl}_y$
$\texttt{area} = \texttt{width} \cdot \texttt{length}$

Implementación

C++JavaPython


long long area(int bl_x, int bl_y, int tr_x, int tr_y) {
	long long length = tr_y - bl_y;
	long long width = tr_x - bl_x;
	return length * width;
}


int area(int bl_x, int bl_y, int tr_x, int tr_y) {
	int length = tr_y - bl_y;
	int width = tr_x - bl_x;
	return length * width;
}


def area(bl_x: int, bl_y: int, tr_x: int, tr_y: int) -> int:
	length = tr_y - bl_y
	width = tr_x - bl_x
	return length * width

Comprobar si dos rectángulos se intersectan

Dados dos rectángulos $a$ y $b$ , solo hay dos casos en los que no se intersectan:

$\texttt{tr}_{a_y}$ $\leq$ $\texttt{bl}_{b_y}$ o $\texttt{bl}_{a_y}$ $\geq$ $\texttt{tr}_{b_y}$ .
$\texttt{bl}_{a_x}$ $\geq$ $\texttt{tr}_{b_x}$ o $\texttt{tr}_{a_x}$ $\leq$ $\texttt{bl}_{b_x}$ .

En todos los demás casos, los rectángulos se intersectan.

Implementación

C++JavaPython


bool intersect(vector<int> s1, vector<int> s2) {
	int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
	int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
 
	// no hay superposición
	if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x || bl_a_y >= tr_b_y || tr_a_y <= bl_b_y) {
		return false;
	} else {
		return true;
	}
}


boolean intersect(int[] s1, int[] s2) {
	int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
	int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
 
	// no hay superposición
	if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x || bl_a_y >= tr_b_y || tr_a_y <= bl_b_y) {
		return false;
	} else {
		return true;
	}
}


def intersect(s1, s2) -> bool:
	bl_a_x, bl_a_y, tr_a_x, tr_a_y = s1[0], s1[1], s1[2], s1[3]
	bl_b_x, bl_b_y, tr_b_x, tr_b_y = s2[0], s2[1], s2[2], s2[3]
 
	# no hay superposición
	if bl_a_x >= tr_b_x or tr_a_x <= bl_b_x or bl_a_y >= tr_b_y or tr_a_y <= bl_b_y:
		return False
	else:
		return True

Calcular el área de intersección

Asumimos que la forma formada por la intersección de dos rectángulos es a su vez un rectángulo.

Primero encontramos el largo y el ancho de este rectángulo. $\texttt{width} = \min(\texttt{tr}_{a_x}, \texttt{tr}_{b_x}) - \max(\texttt{bl}_{a_x}, \texttt{bl}_{b_x})$ . $\texttt{length} = \min(\texttt{tr}_{a_y}, \texttt{tr}_{b_y}) - \max(\texttt{bl}_{a_y}, \texttt{bl}_{b_y})$ .

Si alguno de estos valores es negativo, los rectángulos no se intersectan. Si son cero, se intersectan en un solo punto. Multiplicamos el largo y el ancho para obtener el área de superposición.

Implementación

C++PythonJava


int inter_area(vector<int> s1, vector<int> s2) {
	int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
	int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
 
	return ((min(tr_a_x, tr_b_x) - max(bl_a_x, bl_b_x)) *
	        (min(tr_a_y, tr_b_y) - max(bl_a_y, bl_b_y)));
}


def inter_area(s1, s2) -> int:
	bl_a_x, bl_a_y, tr_a_x, tr_a_y = s1[0], s1[1], s1[2], s1[3]
	bl_b_x, bl_b_y, tr_b_x, tr_b_y = s2[0], s2[1], s2[2], s2[3]
 
	return (min(tr_a_x, tr_b_x) - max(bl_a_x, bl_b_x)) * (
		min(tr_a_y, tr_b_y) - max(bl_a_y, bl_b_y)
	)


int interArea(int[] s1, int[] s2) {
	int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
	int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
	return ((Math.min(tr_a_x, tr_b_x) - Math.max(bl_a_x, bl_b_x)) *
	        (Math.min(tr_a_y, tr_b_y) - Math.max(bl_a_y, bl_b_y)));
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
Bronze	Square Pasture	Fácil	Rectangle	Solución
Bronze	★ Blocked Billboard II	Difícil	Rectangle	Solución
CF	D3C - White Sheet	Difícil	Rectangle	Solución
CF	B. Two Tables	Difícil	Rectangle	Solución