D3C - White Sheet

Solución en video

Por Varun Ragunath

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
 
	// entrada: obtenemos la hoja blanca original
 
	int x1, y1, x2, y2;
 
	cin >> x1 >> y1 >> x2 >> y2;
 
	// actualizamos nuestra hoja blanca con cada nueva hoja negra
	// solo habrá dos iteraciones porque solo hay dos hojas negras
 
	for (int black_sheet = 0; black_sheet < 2; black_sheet++) {
		// entrada: obtenemos la hoja negra actual
		int x3, y3, x4, y4;
		cin >> x3 >> y3 >> x4 >> y4;
 
		// como la hoja blanca tiene que estar cubierta por una hoja negra
		// por completo o tiene que estar cubierta por dos hojas negras con una
		// línea de intersección
 
		// comprobamos si sería posible que la línea separadora
		// sea vertical
		if (y3 <= y1 and y4 >= y2) {
			// los límites del eje y del rectángulo quedan completamente envueltos por la
			// hoja negra: esto es un problema. ahora tenemos que actualizar los límites
			// del eje x. para el límite izquierdo del eje x, comprobamos si
			// está cubierto
			if (x1 >= x3 and x1 <= x4) {
				// ahora sabemos que el límite izquierdo está envuelto, y que
				// hay que actualizarlo al límite derecho de nuestra hoja
				// negra actual
				x1 = x4;
			}
			// aplicamos una lógica similar al límite derecho del eje x
			if (x2 >= x3 and x2 <= x4) { x2 = x3; }
		}
 
		// ahora aplicamos una lógica similar por si la línea separadora
		// fuera horizontal
		if (x3 <= x1 and x4 >= x2) {
			// completamente envuelto, así que hay que actualizar el borde
			// para actualizar el borde aplicamos la misma lógica de antes
			if (y1 >= y3 and y1 <= y4) { y1 = y4; }
			// lo mismo aquí
			if (y2 >= y3 and y2 <= y4) { y2 = y3; }
		}
	}
 
	// ahora hay que comprobar y confirmar que nuestro rectángulo no es degenerado
 
	if (x2 > x1 and y2 > y1) {
		// como no es degenerado, cualquier punto dentro de nuestro rectángulo actual
		// sirve como un punto posible
		cout << "YES\n";
	} else {
		// uno de los lados del rectángulo es degenerado, así que no hay
		// punto visible
		cout << "NO\n";
	}
 
	return 0;
}


import java.util.*;
public class whiteSheet {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// entrada: obtenemos la hoja blanca original
 
		int x1, y1, x2, y2;
 
		x1 = sc.nextInt();
		y1 = sc.nextInt();
		x2 = sc.nextInt();
		y2 = sc.nextInt();
 
		// actualizamos nuestra hoja blanca con cada nueva hoja negra
		// solo habrá dos iteraciones porque solo hay dos hojas
		// negras
 
		for (int black_sheet = 0; black_sheet < 2; black_sheet++) {
			// entrada: obtenemos la hoja negra actual
			int x3, y3, x4, y4;
			x3 = sc.nextInt();
			y3 = sc.nextInt();
			x4 = sc.nextInt();
			y4 = sc.nextInt();
 
			// como la hoja blanca tiene que estar cubierta por una hoja
			// negra por completo o tiene que estar cubierta por dos hojas negras con
			// una línea de intersección
 
			// comprobamos si sería posible que la línea
			// separadora sea vertical
			if (y3 <= y1 && y4 >= y2) {
				// los límites del eje y del rectángulo quedan completamente envueltos por
				// la hoja negra: esto es un problema. ahora tenemos que actualizar los
				// límites del eje x. para el límite izquierdo del eje x, comprobamos
				// si está cubierto
				if (x1 >= x3 && x1 <= x4) {
					// ahora sabemos que el límite izquierdo está envuelto, y que
					// hay que actualizarlo al límite derecho de nuestra
					// hoja negra actual
					x1 = x4;
				}
				// aplicamos una lógica similar al límite derecho del eje x
				if (x2 >= x3 && x2 <= x4) { x2 = x3; }
			}
 
			// ahora aplicamos una lógica similar por si la línea separadora
			// fuera horizontal
			if (x3 <= x1 && x4 >= x2) {
				// completamente envuelto, así que hay que actualizar el borde
				// para actualizar el borde aplicamos la misma lógica de antes
				if (y1 >= y3 && y1 <= y4) { y1 = y4; }
				// lo mismo aquí
				if (y2 >= y3 && y2 <= y4) { y2 = y3; }
			}
		}
 
		// ahora hay que comprobar y confirmar que nuestro rectángulo no es degenerado
 
		if (x2 > x1 && y2 > y1) {
			// como no es degenerado, cualquier punto dentro de nuestro
			// rectángulo actual sirve como un punto posible
			System.out.println("YES");
		} else {
			// uno de los lados del rectángulo es degenerado, así que no hay
			// punto visible
			System.out.println("NO");
		}
	}
}

Análisis oficial (C++)

Explicación

Hay muchas formas de resolver el problema, pero la más fácil es imaginar que cortamos la hoja blanca.

Cada vez que la hoja blanca queda cubierta por una hoja negra, podemos imaginar que cortamos la intersección entre las hojas negra y blanca. Luego, si el área de la hoja blanca final después de ser cortada por los dos rectángulos es mayor que cero, hay una porción de la hoja blanca que es visible.

Sin embargo, al considerar el corte de la hoja, la porción que se corta debe cortarse por completo de $x_{1}$ -> $x_{2}$ o de $y_{1}$ -> $y_{2}$ ; de lo contrario quedará una porción de la hoja blanca todavía visible. Solo cortamos cuando una hoja negra cubre por completo todo el ancho o todo el largo de la hoja blanca; si no, seguirán viéndose trozos.

Hay 4 instancias en las que una hoja blanca puede quedar cubierta por una hoja negra.

$\textbf{Arriba: }$ Desde arriba, si la hoja blanca queda completamente cubierta de $x_{1}$ -> $x_{2}$ o de $y_{1}$ -> $y_{2}$ e intersecta alguna parte de una hoja negra, entonces cambiamos $y_{2}$ (parte superior del rectángulo) al borde inferior del rectángulo negro.

$\textbf{Abajo: }$ Desde abajo, si la hoja blanca queda completamente cubierta de $x_{1}$ -> $x_{2}$ e intersecta alguna parte de una hoja negra, entonces cambiamos $y_{1}$ (parte inferior del rectángulo) al borde superior del rectángulo negro.

$\textbf{Izquierda: }$ Desde la izquierda, si la hoja blanca queda completamente cubierta de $y_1$ a $y_2$ e intersecta alguna parte de una hoja negra, entonces cambiamos $x_1$ (borde izquierdo del rectángulo) al borde derecho del rectángulo negro.

$\textbf{Derecha: }$ Desde la derecha, si la hoja blanca queda completamente cubierta de $y_1$ a $y_2$ e intersecta alguna parte de una hoja negra, entonces cambiamos $x_2$ (borde derecho del rectángulo) al borde izquierdo del rectángulo negro.

También hay que asegurarse de que $x_1$ sea siempre $<$ $x_2$ y lo mismo con $y_1$ e $y_2.$

Como no hay bucles for ni ningún tipo de repeticiones, la complejidad temporal es $\mathcal{O}(1)$

Implementación

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

C++PythonJava


#include <bits/stdc++.h>
using namespace std;
 
struct Rect {
	int x1, y1, x2, y2;
	int area() { return (x2 - x1) * (y2 - y1); }
};
 
/*
   Idea principal: si B intersecta por completo en la dirección x o y, lo cortamos.
   Este método corta el rectángulo A según el rectángulo B. (A - hoja blanca, B -
   hoja negra) Podemos cortar el rectángulo A si B cubre todo x1->x2 o y1->y2.
 */
Rect cut(Rect A, Rect B) {
	// Si B corta A desde el lado izquierdo
	if (A.x1 >= B.x1 && B.x2 >= A.x1 && B.y1 <= A.y1 && B.y2 >= A.y2) {
		A.x1 = B.x2;
		A.x2 = max(A.x2, B.x2);  // Si B cubre A por completo
	}
 
	// Si B corta A desde el lado derecho
	if (A.x2 >= B.x1 && B.x2 >= A.x2 && B.y1 <= A.y1 && B.y2 >= A.y2) {
		A.x2 = B.x1;
		A.x1 = min(A.x1, B.x1);  // Si B cubre A por completo
	}
 
	// Si B corta A desde el lado inferior
	if (A.y1 >= B.y1 && B.y2 >= A.y1 && B.x1 <= A.x1 && B.x2 >= A.x2) {
		A.y1 = B.y2;
		A.y2 = max(A.y2, B.y2);  // Si B cubre A por completo
	}
 
	// Si B corta A desde el lado superior
	if (A.y2 >= B.y1 && B.y2 >= A.y2 && B.x1 <= A.x1 && B.x2 >= A.x2) {
		A.y2 = B.y1;
		A.y1 = min(A.y1, B.y1);  // Si B cubre A por completo
	}
	return A;
}
 
int main() {
	Rect A, B, C;
	cin >> A.x1 >> A.y1 >> A.x2 >> A.y2;
	cin >> B.x1 >> B.y1 >> B.x2 >> B.y2;
	cin >> C.x1 >> C.y1 >> C.x2 >> C.y2;
 
	A = cut(A, B);
	A = cut(A, C);
	// Imprimimos NO solo si el área cortada restante es 0.
	if (A.area() == 0) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	}
}


class Rect:
	def __init__(self, a: int, b: int, c: int, d: int):
		self.x1, self.y1, self.x2, self.y2 = a, b, c, d
 
 
"""
Idea principal: si B intersecta por completo en la dirección x o y, lo cortamos.
Este método corta el rectángulo A según el rectángulo B. (A - hoja blanca, B - hoja negra)
Podemos cortar el rectángulo A si B cubre todo x1->x2 o y1->y2.
"""
 
 
def cut(A: Rect, B: Rect) -> Rect:
	# Si B corta A desde el lado izquierdo
	if A.x1 >= B.x1 and B.x2 >= A.x1 and B.y1 <= A.y1 and B.y2 >= A.y2:
		A.x1 = B.x2
		A.x2 = max(A.x2, B.x2)  # Si B cubre A por completo
 
	# Si B corta A desde el lado derecho
	if A.x2 >= B.x1 and B.x2 >= A.x2 and B.y1 <= A.y1 and B.y2 >= A.y2:
		A.x2 = B.x1
		A.x1 = min(A.x1, B.x1)  # Si B cubre A por completo
 
	# Si B corta A desde el lado inferior
	if A.y1 >= B.y1 and B.y2 >= A.y1 and B.x1 <= A.x1 and B.x2 >= A.x2:
		A.y1 = B.y2
		A.y2 = max(A.y2, B.y2)  # Si B cubre A por completo
 
	# Si B corta A desde el lado superior
	if A.y2 >= B.y1 and B.y2 >= A.y2 and B.x1 <= A.x1 and B.x2 >= A.x2:
		A.y2 = B.y1
		A.y1 = min(A.y1, B.y1)  # Si B cubre A por completo
 
	return A
 
 
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
Z = list(map(int, input().split()))
 
A = Rect(X[0], X[1], X[2], X[3])
B = Rect(Y[0], Y[1], Y[2], Y[3])
C = Rect(Z[0], Z[1], Z[2], Z[3])
 
A = cut(A, B)
A = cut(A, C)
 
# Imprimimos NO solo si el área cortada restante es 0.
print("NO" if A.x2 - A.x1 == 0 or A.y2 - A.y1 == 0 else "YES")


import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		Rect A = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());
		Rect B = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());
		Rect C = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());
 
		A = cut(A, B);
		A = cut(A, C);
 
		// Imprimimos NO solo si el área cortada restante es 0.
		if (A.area() == 0) {
			System.out.println("NO");
		} else {
			System.out.println("YES");
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
 
	static class Rect {
		public int x1, y1, x2, y2;
		public Rect(int a, int b, int c, int d) {
			x1 = a;
			y1 = b;
			x2 = c;
			y2 = d;
		}
 
		public int area() { return (x2 - x1) * (y2 - y1); }
	}
 
	/*
	   Idea principal: si B intersecta por completo en la dirección x o y, lo cortamos.
	   Este método corta el rectángulo A según el rectángulo B. (A - hoja blanca, B -
	   hoja negra) Podemos cortar el rectángulo A si B cubre todo x1->x2 o y1->y2.
	 */
	static Rect cut(Rect A, Rect B) {
 
		// Si B corta A desde el lado izquierdo
		if (A.x1 >= B.x1 && B.x2 >= A.x1 && B.y1 <= A.y1 && B.y2 >= A.y2) {
			A.x1 = B.x2;
			A.x2 = Math.max(A.x2, B.x2);  // Si B cubre A por completo
		}
 
		// Si B corta A desde el lado derecho
		if (A.x2 >= B.x1 && B.x2 >= A.x2 && B.y1 <= A.y1 && B.y2 >= A.y2) {
			A.x2 = B.x1;
			A.x1 = Math.min(A.x1, B.x1);  // Si B cubre A por completo
		}
 
		// Si B corta A desde el lado inferior
		if (A.y1 >= B.y1 && B.y2 >= A.y1 && B.x1 <= A.x1 && B.x2 >= A.x2) {
			A.y1 = B.y2;
			A.y2 = Math.max(A.y2, B.y2);  // Si B cubre A por completo
		}
 
		// Si B corta A desde el lado superior
		if (A.y2 >= B.y1 && B.y2 >= A.y2 && B.x1 <= A.x1 && B.x2 >= A.x2) {
			A.y2 = B.y1;
			A.y1 = Math.min(A.y1, B.y1);  // Si B cubre A por completo
		}
		return A;
	}
}