Google Code Jam 2010: Rope Internet

Rope Internet foi o primeiro problema da rodada 1C. O enunciado oficial está aqui; considere a figura abaixo que mostra uma série de segmentos de reta unindo dois prédios:


O problema consiste em, dadas as alturas A e B das extremidades das retas, determinar quantas intersecções ocorrem. Para simplificar, é garantido que nenhum par de segmentos começa ou termina na mesma altura e que nunca ocorre de mais de dois segmentos cruzarem no mesmo ponto.

A quantidade de segmentos nos arquivos de teste é baixa: máximo de 2 no small input e 1000 no large input. Isto significa que, se o teste da intersecção de duas retas for rápido, dá para analisar todos os pares (serão no máximo 1 milhão de pares a testar).

Uma primeira observação importante é que a distância entre os dois prédios não é dada; o resultado independe dela. Vamos considerar que a coordenada horizontal do prédio da esquerda é zero e a do prédio da direita é 1. Usando a tradicional equação da reta (Y = aX + b) podemos calcular a coordenada horizontal da intersecção do segmento de (0, Ai) a (1, Bi) com o segmento de (0, Aj) a (1, Bj):

1o segmento: Y = Ai + (Bi-Ai) * X
2o segmento: Y = Aj + (Bj-Aj) * X

na intersecção o Y é igual para os dois segmentos logo:

Ai + (Bi-Ai) * X = Aj + (Bj-Aj) * X

resolvendo esta equação para X, obtemos

X = (Aj - Ai) / (Bi - Ai - Bj + Aj)

Se (Bi - Ai - Bj + Aj) for zero, não teremos intersecção (os segmentos são paralelos). Para termos uma intersecção entre os prédios, X precisa estar entre 0 e 1 (pelo enunciado não pode ser exatamente 0 ou 1). Resta notar que não precisamos calcular a divisão ou trabalhar com números fracionários:

• Se o sinal de (Aj - Ai) for diferente do de (Bi - Ai - Bj + Aj), o resultado será menor que 0.
• Se os sinais forem iguais e |Aj - Ai| for maior que |Bi - Ai - Bj + Aj| o resultado será maior que 1.

Chegamos assim ao meu programa:

//
// Google CodeJam 2010 - Round 1C, Problem A
// DQuadros
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int a[1000], b[1000];
int N;

void main (void)
{
  int iCase, nCases;
  int i, j, ni;
  int da, db;

  scanf ("%d\n", &nCases);
  for (iCase = 1; iCase <= nCases; iCase++)
  {
      scanf ("%d\n", &N);
      for (i = 0; i < N; i++)
          scanf ("%d %d\n", &a[i], &b[i]);

      ni = 0;
      for (i = 0; i < N; i++)
      {
          for (j = i; j < N; j++)
          {
              da = a[j] - a[i];
              db = b[i]-a[i]-b[j]+a[j];
              if (db != 0)
              {
                  if (da > 0)
                  {
                      if (db > da)
                          ni++;
                  }
                  else
                  {
                      if (-db > -da)
                          ni++;
                  }
              }

          }
      }
      printf ("Case #%d: %d\n", iCase, ni);
  }
}