Como você mesmo reparou, esse problema pode ser reduzido de cobertura de área para cobertura de segmentos. A título de nivelar quem chegar nesta questão, vou explicar essa transformação. E a área, por incrível que pareça, não é relevante para a questão por um detalhe simples: o enunciado garantiu que todos os borrifadores estarão exatamente no centro.
Assim, o terreno que nos é fornecido é algo assim:

De modo geral, você só encontrará estes seguintes 3 tipos de círculos nessa linha central:

- o primeiro é um círculo que tem um diâmetro de irrigação menor do que
W
- o círculo do meio é aquele que tem um diâmetro maior do que
W
- o último círculo é aquele que tem um diâmetro de irrigação idêntico a
W
Nesse tipo de caso, os pontos mais distantes da linha central do retângulo são aqueles que são mais difíceis de serem regados. Se esse ponto for regado, eu tenho por garantia que todo o segmento vertical associado a esse ponto fixo também é regado.
Então, assim sendo, nosso problema acaba sendo transformado em cobrir esses pontos extremos. Ou seja, cobrir um segmento inteiro.
Então, como faço para transformar o problema de áreas de círculos dentro do retângulo para segmentos?
Primeiro, vamos entender como cada tipo de círculo vai ser projetado no segmento inferior do retângulo (poderia usar simetricamente o superior, apenas escolhi uma projeção conveniente para fazer o desenho)?
O primeiro tipo de círculo não alcança a borda, logo ele não é útil em regar na borda inferior e sempre é desnecessário.
O segundo tipo vai projetar todo um intervalo, como ilustrado abaixo:

O raio do círculo foi ilustrado em vermelho, o segmento projetado do círculo foi indicado em ciano. O cálculo para saber onde começa e onde termina esse segmento já está na pergunta: [ x-sqrt(r^2 - (w/2)^2) , x+sqrt(r^2 - (w/2)^2) ]
, onde x
é a posição do borrifador, r
o seu raio e w
a largura do campo.
Como se chegou nesses valores? Se você fizer um segmento do centro do círculo até a parte inferior do retângulo de maneira perpendicular, perceberá que ele cairá exatamente no meio do segmento. Assim, como ele é perpendicular, se unir esse segmento, um dos raios e pegar o segmento da ponta do segmento perpendicular obterá um triângulo retângulo. A hipotenusa é conhecida, o raio do círculo, r
; um dos catetos também é conhecido, que é o comprimento do segmento perpendicular do centro do círculo até o retângulo, que é metade da largura do campo, portanto w/2
; sobrando então o outro cateto para se calcular o comprimento que é sqrt(r^2 - (w/2)^2)
. Então, se eu pegar o ponto do centro do círculo e andar para a esquerda, obtenho o ponto a esquerda do segmento como sendo x-sqrt(r^2 - (w/2)^2)
, e se andar para a direita x+sqrt(r^2 - (w/2)^2)
.
O terceiro tipo de círculo adicionará apenas um ponto no segmento inferior. Como estamos tratando de uma quantidade finita de círculos, a união de muitos pontos nunca chegará a fazer um segmento, logo esse tipo de borrifador também não contribuirá para fazer a irrigação, assim como o primeiro tipo de borrifador.
Dito isso, vamos começar a montar o algoritmo?
Primeiro, vamos precisar ler todos os pontos. Então, descartaremos os círculos que não contribuirão para fazer o intervalo; ou seja, ficaremos apenas com círculos cujos raios sejam estritamente maiores do que metade da largura. Então, transformamos os círculos filtrados em intervalos.
Pronto, agora temos apenas intervalos e desejamos saber qual o menor conjunto desses intervalos que cobrem todo um segmento. Sabe o que podemos usar para modelar interseções de intervalos? Um grafo de intervalos!
Sim, agora estou transformando o problema em em problema de grafos. Como montar esse grafo?
Um grafo de intervalo é uma maneira de representar, em grafo, segmentos e interseções. Cada segmento é um vértice e a existência de interseções entre dois intervalos é representado como uma aresta. Então, com o grafo montado, Precisamos sair de algum intervalo que contenha o 0
(origem) e, apenas navegando pelas arestas, chegar em algum intervalo que contenha o L
(destino). Se não for possível, seja porque não tem nenhum intervalo que contenha o 0
para partida, seja porque não tem nenhum ponto de chegada que contenha o L
ou porque o grafo é disconexo, então retorno -1
.
Aqui na rede tem algumas perguntas interessantes que abordam o problema de grafos de intervalo. As que eu me lembro no momento:
Inclusive, sugiro a leitura nessa ordem que coloquei, que não por acaso coincide com a ordem cronológica de publicação
O primeiro passo é descobrir qual o vértice de partida. Independente de qualquer coisa, o ponto de partida precisa englobar o ponto 0
. Portanto, devo considerar como vértice candidato à partida todo intervalo cujo valor mais a esquerda é <=0
. Similarmente com o vértice de chegada, valor mais a direita >=L
.
Agora, como definir de maneiras mais assertivas esses pontos? Para o ponto de partida, aquele que cobrir até o máximo a direita terá cobertura total sobre qualquer outro ponto candidato de partida, portanto sobra apenas aquele cujo valor mais a direita é o maior. De maneira semelhante, o ponto de chegada é aquele cujo valor mais a esquerda é o menor.
Tem o caso especial de que o ponto de partida engloba a saída; nesse caso, existe ainda a possibilidade de que o meu detector de origem/destino encontre pontos distintos de origem e destino, mas é trivial verificar se apenas o borrifador de origem seria o suficiente para cobrir tudo. Para esse caso, basta retornar 1
e ir para a próxima entrada.
Definidos origem e destino, precisamos das arestas para navegar no grafo. A priori, um grafo de intervalo é um grafo não-direcionado. Porém, podemos fazer algumas otimizações e transformar nosso grafo de intervalo num grafo direcionado acíclico.
Eu vou adicionar uma aresta do intervalo [c1, f1]
para o intervalo [c2, f2]
se e somente se existir interseção entre esses intervalos e o segundo intervalo terminar depois do primeiro intervalo e o segundo intervalo não englobar totalmente o primeiro. Ou seja, se c2 <= f1
(precisa haver interseção) e f2 > f1
(o segundo intervalo necessariamente termina depois do primeiro intervalo) e c2 > c1
(o primeiro intervalo tem um pedaço anterior ao segundo intervalo). Obviamente que ordenar os intervalos pelo seu valor a esquerda de modo crescente nos permite fazer diversas otimizações na construção das arestas
Montando esse grafo, direcionado mesmo, basta rodar qualquer algoritmo de menor distância entre vértices (considere todas as arestas com peso 1) do ponto de origem até o ponto de destino. Se não for possível alcançar o destino, a saída precisa ser -1
. Caso contrário, a saída é a distância encontrada mais um.
Pelo que entendi da sua abordagem, você tentou fazer algo mais guloso. Porém, a estratégia gulosa para funcionar precisa decidir com muita calma se deve inserir ou não o próximo intervalo. Pelo que pude olhar, a estratégia de escolher o próximo elemento que você usou foi realmente adequada (olho para frente todos os intervalos que tem alguma interseção com o que já foi coberto até o momento). Porém a escolha do ponto de partida é sempre fixa, não se tenta otimizá-lo para pegar como partida aquele que contém o 0
e vai até o mais longe possível. Aí, sim, você teria uma solução gulosa e sem backtracking.
Também percebi que você adiciona desnecessariamente na lista pontos que eu filtrei fora, fazendo eles serem um peso na ordenação que seria desnecessário (mas que no final das contas não seria significativo).