Esta es una pregunta de entrevista, la entrevista ya se realizó.

Dado un mazo de cartas rectangulares, colóquelas al azar en una mesa rectangular cuyo tamaño sea mucho mayor que la suma total del tamaño de las cartas. Algunas cartas pueden superponerse entre sí al azar. Diseñe un algoritmo que pueda calcular el área que cubre la tabla con todas las tarjetas y también analice la complejidad temporal del algoritmo. Se conocen todas las coordenadas de cada vértice de todas las cartas. Las tarjetas pueden superponerse en cualquier patrón.

Mi idea

Ordene las tarjetas por su orden descendente de coordenadas verticales.

Escanee las tarjetas verticalmente de arriba a abajo después de alcanzar un borde o vértices de una tarjeta, siga escaneando con otra línea de escaneo hasta que llegue a otro borde y encuentre el área ubicada entre las dos líneas. Finalmente, sume toda el área ubicada entre dos líneas y obtenga el resultado.

Pero, cómo calcular el área ubicada entre dos líneas es un problema si el área es irregular.

Cualquier ayuda es apreciada. Gracias