Hay una gran parcela con varios sumideros presentes. Dado que un sumidero puede combinarse con otro sumidero, se requiere obtener como máximo un sumidero mientras se ocupa la parcela. Tienes que encontrar el área cuadrada máxima formada con al menos un sumidero presente. Si hay dos parcelas con la misma área, imprima la que tenga el menor sumidero presente; de lo contrario, si los sumideros también son iguales, imprima cualquiera. Para cada caso, debe imprimir la coordenada inferior izquierda y el punto superior derecho. Tenga en cuenta que la trama comienza con (1, 1).
Límite de tiempo = 1 segundo y límite de memoria : 256 Mb
Entrada: la primera línea dará el número de casos de prueba. Para cada caso de prueba, se nos dará el tamaño de la array de la trama N x M (donde 1<=N, M<=1000). La siguiente línea dará el número de sumideros presentes en la array K (1<=K<=N+M). A continuación, las líneas K darán las coordenadas de los sumideros.
Salida: Para cada caso de prueba, debe imprimir el número del caso de prueba y las coordenadas del cuadrado resultante. es decir , #i xb yb xt yt (caso de prueba, xb=coordenada x inferior izquierda, yb=coordenada y inferior izquierda, xt=coordenada x superior derecha, yt=coordenada y superior derecha)
Ejemplo:
yo/p:
1
6 6
4
1 1
3 3
4 4
6 6
Matrix Formed se verá algo como esto:
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0
o/p:
#1 1 4 3 6
Veredicto: resolví usando fuerza bruta con O (n ^ 4) y obtuve TLE. Así que no fue seleccionado. ¡No estoy seguro, pero cualquier enfoque con O (n ^ 3) debería funcionar!
Publicación traducida automáticamente
Artículo escrito por Niteesh Tiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA