Solução por Pedro Racchetti
Conteúdos utilizados:
- Prefixos e Sufixos
- Intersecção de retângulos
Para resolver esse problema, precisamos entender a ideia de intersecção de retângulos. É fácil perceber que um retângulo $$i$$ faz intersecção com um retângulo $$j$$ se $$X1_i \geq X1_j$$ e $$X1_i \leq X2_j$$ e $$Y1_i \geq Y1_j$$ e $$Y1_i \leq Y2_j$$ . Além disso, nota-se que o ponto descrito no problema tem que estar na intersecção de pelo menos $$n – 1$$ retângulos. Podemos portanto, fazer uma função que retorna essa intersecção, caso exista, da seguinte maneira:
https://gist.github.com/PedroRacchetti/0a42a4fed24686856769062650f4c2fc
Sabendo disso, podemos manter um vetor de prefixos das intersecções, de modo que a posição $$i$$ guarde a intersecção de todos os retângulos $$j$$ tal que $$i < j$$ (se tal intersecção não exista, podemos usar um retângulo nulo, que represente que não há intersecção, alterando a função acima), e um vetor análogo aos sufixos. Verificamos então se existe uma intersecção no fim do vetor de prefixos ou uma no início do vetor de sufixos, caso existir, podemos imprimir qualquer ponto dessas intersecções, já que é uma intersecção com todos os retângulos, menos o último ou o primeiro, respectivamente. Caso não exista, iteramos de $$1$$ à $$n – 2$$, e verificar se existe a intersecção do prefixo de $$i – 1$$ com o sufixo de $$i + 1$$, quando existir, imprimimos qualquer ponto dessa intersecção e finalizamos o programa.
Segue o código para melhor entendimento da solução:
https://gist.github.com/PedroRacchetti/c3ec6e822f39b9b8994d1a9e6eaebb8c