B. Two Tables

Explicación

Llamemos:

$x_{1}$ y $x_{2}$ a los puntos más a la izquierda y más a la derecha de la mesa 1 respectivamente
$y_{1}$ y $y_{2}$ a los puntos más abajo y más arriba de la mesa 1 respectivamente
$w_{1}$ y $h_{1}$ al ancho y alto de la mesa 1 (iguales a la diferencia entre $x_{1}$ y $x_ {2}$ y entre $y_{1}$ e $y_{2}$ respectivamente)
$w_{2}$ y $h_{2}$ al ancho y alto de la mesa 2 respectivamente
$W$ y $H$ al ancho y alto de la habitación respectivamente

La clave de este problema es darse cuenta de que la mesa 2 solo estará alguna vez en 4 posiciones distintas relativas a la mesa 1: a su izquierda, derecha, arriba o abajo (véase el diagrama de abajo). Además, en todos los casos podemos asumir que la mesa 2 estará tocando su pared respectiva para (intentar) maximizar su distancia a la mesa 1. Por ejemplo, si colocamos la mesa 2 a la izquierda de la mesa 1, asumiremos que su borde izquierdo toca la pared izquierda de la habitación. Determinar la solución es entonces simplemente simular todos estos casos y hallar cuál implica mover la mesa 1 la menor distancia.

Posibles colocaciones de la mesa 2 relativas a la mesa 1.

Para determinar la distancia mínima que hay que mover la mesa 1, tenemos que calcular la superposición entre las dos mesas. Por ejemplo:

En este caso, la mesa 2 se coloca a la izquierda de la mesa 1. Por lo tanto, podemos calcular su superposición con la mesa 1 así: $w$ - $x_{1}$ . Aquí la superposición es 1, lo que significa que debemos mover la mesa 1 un espacio desde su posición inicial para que quepa la mesa 2 en la habitación. Luego comparamos esta respuesta con las que obtenemos al colocar la mesa 2 a la derecha, arriba o abajo de la mesa 1. La menor de todas es nuestra respuesta final.

Para resumir, calculamos la superposición de las dos mesas así:

Mesa 2 colocada a la izquierda de la mesa 1: Superposición = $w$ - $x_{1}$
Mesa 2 colocada a la derecha de la mesa 1: Superposición = $x_{2}$ - ( $W$ - $w$ )
Mesa 2 colocada arriba de la mesa 1: Superposición = $y_{2}$ - ( $H$ - $h$ )
Mesa 2 colocada abajo de la mesa 1: Superposición = $h$ - $y_{1}$

Es posible que las dos mesas no se superpongan en absoluto. En ese caso, los cálculos de arriba devolverían un número negativo, así que en su lugar debemos devolver 0 para indicar que la mesa 1 no tiene que moverse.

Implementación

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

C++PythonJava


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		int total_width, total_height;
		cin >> total_width >> total_height;
 
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
 
		int w1 = x2 - x1;
		int h1 = y2 - y1;
 
		int w2, h2;
		cin >> w2 >> h2;
 
		// Calculamos los valores mín y máx de X e Y necesarios para que quepan en su sitio
		int left_place = w2;
		int right_place = total_width - w2;
		int top_place = total_height - h2;
		int bottom_place = h2;
 
		// Calculamos la distancia necesaria para mover el primer rectángulo
		int amount_needed_left = max(left_place - x1, 0);
		int amount_needed_right = max(x2 - right_place, 0);
		int amount_needed_top = max(y2 - top_place, 0);
		int amount_needed_bottom = max(bottom_place - y1, 0);
 
		// Comprobamos los límites de los rectángulos
		if (w1 + w2 > total_width) {
			amount_needed_left = INT32_MAX;
			amount_needed_right = INT32_MAX;
		}
 
		if (h1 + h2 > total_height) {
			amount_needed_top = INT32_MAX;
			amount_needed_bottom = INT32_MAX;
		}
 
		// truco práctico para obtener el mín de varios elementos
		int ans = min({amount_needed_left, amount_needed_right, amount_needed_top,
		               amount_needed_bottom});
 
		// si los rectángulos no caben en el rectángulo más grande de ninguna forma,
		// imprimimos -1
		cout << (ans == INT32_MAX ? -1 : ans) << endl;
	}
}


for _ in range(int(input())):
	total_width, total_height = map(int, input().split())
	x1, y1, x2, y2 = map(int, input().split())
	w1 = x2 - x1
	h1 = y2 - y1
	w2, h2 = map(int, input().split())
 
	ans = float("inf")
 
	# Calculamos los valores mínimo y máximo de X e Y necesarios para que quepan en su sitio
	left_place = w2
	right_place = total_width - w2
	top_place = total_height - h2
	bottom_place = h2
 
	# Calculamos la distancia necesaria para mover el primer rectángulo
	amount_needed_left = max(left_place - x1, 0)
	amount_needed_right = max(x2 - right_place, 0)
	amount_needed_top = max(y2 - top_place, 0)
	amount_needed_bottom = max(bottom_place - y1, 0)
 
	# Comprobamos los límites de los rectángulos
	if w1 + w2 > total_width:
		amount_needed_left = float("inf")
		amount_needed_right = float("inf")
 
	if h1 + h2 > total_height:
		amount_needed_top = float("inf")
		amount_needed_bottom = float("inf")
 
	# truco práctico para obtener el mín de varios elementos
	ans = min(
		amount_needed_left, amount_needed_right, amount_needed_top, amount_needed_bottom
	)
 
	# si ans es float('inf'), no hay forma de que quepan los dos rectángulos en la habitación
	print(ans if ans != float("inf") else -1)


import java.io.*;
import java.util.*;
 
public class TwoTables {
	static InputReader r = new InputReader(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) {
		int n = r.nextInt();
 
		for (int i = 0; i < n; i++) {
			int W = r.nextInt();
			int H = r.nextInt();
			int x1 = r.nextInt();
			int y1 = r.nextInt();
			int x2 = r.nextInt();
			int y2 = r.nextInt();
			int w = r.nextInt();
			int h = r.nextInt();
 
			int answer = Integer.MAX_VALUE;
 
			// Comprobamos si los anchos combinados de las mesas caben en la habitación
			if ((x2 - x1) + w <= W) {
				// Determinamos la superposición al colocar la mesa a la izquierda
				int left = Math.max(0, w - x1);
				// Determinamos la superposición al colocar la mesa a la derecha
				int right = Math.max(0, x2 - (W - w));
				answer = Math.min(left, right);
			}
 
			// Comprobamos si las alturas combinadas de las mesas caben en la habitación
			if ((y2 - y1) + h <= H) {
				int top = Math.max(0, y2 - (H - h));
				int bottom = Math.max(0, h - y1);
				int minTB = Math.min(top, bottom);
				answer = Math.min(answer, minTB);
			}
 
			pw.println(answer == Integer.MAX_VALUE ? -1 : answer);
		}
		pw.close();
	}
 
	// BeginCodeSnip{I/O Template}
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
 
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
 
		String next() {  // lee el siguiente string
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) { throw new RuntimeException(e); }
			}
			return tokenizer.nextToken();
		}
 
		public int nextInt() {  // lee el siguiente int
			return Integer.parseInt(next());
		}
 
		public long nextLong() {  // lee el siguiente long
			return Long.parseLong(next());
		}
 
		public double nextDouble() {  // lee el siguiente double
			return Double.parseDouble(next());
		}
	}
	// EndCodeSnip
}