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:

view plaincopy to clipboardprint?

1. //  
2. // Google CodeJam 2010 - Round 1C, Problem A  
3. // DQuadros  
4. //  
5. #include <stdio.h>  
6. #include <stdlib.h>  
7. #include <string.h>  
8.   
9. int a[1000], b[1000];  
10. int N;  
11.   
12. void main (void)  
13. {  
14.   int iCase, nCases;  
15.   int i, j, ni;  
16.   int da, db;  
17.   
18.   scanf ("%d\n", &nCases);  
19.   for (iCase = 1; iCase <= nCases; iCase++)  
20.   {  
21.       scanf ("%d\n", &N);  
22.       for (i = 0; i < N; i++)  
23.           scanf ("%d %d\n", &a[i], &b[i]);  
24.   
25.       ni = 0;  
26.       for (i = 0; i < N; i++)  
27.       {  
28.           for (j = i; j < N; j++)  
29.           {  
30.               da = a[j] - a[i];  
31.               db = b[i]-a[i]-b[j]+a[j];  
32.               if (db != 0)  
33.               {  
34.                   if (da > 0)  
35.                   {  
36.                       if (db > da)  
37.                           ni++;  
38.                   }  
39.                   else  
40.                   {  
41.                       if (-db > -da)  
42.                           ni++;  
43.                   }  
44.               }  
45.   
46.           }  
47.       }  
48.       printf ("Case #%d: %d\n", iCase, ni);  
49.   }  
50. }  

//
// 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);
  }
}