Descrição
Uma das principais dificuldades de organizar uma Maratona de Programação é recolher os bal˜oes que escapam e ficam presos no teto do salão: muitas vezes o contrato com o dono do salão exige que este seja entregue limpo logo após o evento, sob pena de multa.
Este ano a organização da Maratona está mais previdente: ela tem o desenho do teto do salão, e quer sua ajuda para determinar o que pode acontecer com um balão, dependendo da posição no solo onde ele é solto (isto é, se é bloqueado pelo teto ou se escapa para o exterior do salão).
O teto do salão é formado por vários planos que, vistos de lado, podem ser descritos por segmentos de reta, como mostrado na figura abaixo:
O balão pode ser considerado pontual. Quando um balão toca um segmento do teto que é horizontal, ele fica preso. Quando um balão toca um segmento que é inclinado, o balão desliza até o ponto mais alto do segmento e escapa, podendo escapar completamente do salão ou podendo tocar em mais segmentos. Não há pontos em comum entre os segmentos que formam o teto.
Por exemplo, se o balão for solto nas posições marcadas como a ou b, será bloqueado na posição de coordenadas (2, 5); se o balão for solto na posição marcada como c, será bloqueado na posição de coordenadas (6, 5); e se o balão for solto na posição marcada como d, não será bloqueado e escapará para fora do salão na posição de coordenada x = 7.
Escreva um programa que, dada a descrição do teto do salão como segmentos de reta, responde a uma série de consultas sobre a posição final de bal˜oes soltos do piso do salão.
Entrada
A primeira linha da entrada contém dois inteiros N e C indicando, respectivamente, o número de segmentos de reta do teto e o número de consultas. Cada uma das N linhas seguintes contém quatro inteiros X 1 , Y 1 , X 2 , Y 2 , descrevendo um segmento de reta do perfil do teto, com extremos de coordenadas (X 1 , Y 1 ) e (X 2 , Y 2 ).
Cada uma das C linhas seguintes descreve uma consulta e contém um inteiro X, indicando que a consulta quer determinar o que acontece com um balão solto no ponto de coordenada (X, 0).
Saída
Para cada consulta da entrada, seu programa deve imprimir uma única linha. Se o balão escapar do salão, a linha deve conter um único inteiro X, indicando a coordenada x pela qual o balão escapa do salão. Caso contrário, a linha deve conter dois inteiros X e Y indicando a posição (x, y) em que o balão fica retido no teto.
Restrições
• 1 ≤ N ≤ 105
• 1 ≤ C ≤ 105
• 0 ≤ X1 , X2 ≤ 106 , 0 < Y1 , Y2 ≤ 106 , X1 != X2
• não há dois valores de coordenadas x iguais, considerando todos os segmentos.
• 0 ≤ X ≤ 106
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 3 |
1 |
|
4 4 |
2 5 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: Maratona de Programação da SBC 2013