Mini-Concurso de programacion

[jgpeiro06]

Hola a todos!

Se me ha ocurrido plantear un concurso o reto a todos los programadores de todopic.
El concursante debe implementar una función que determine si un punto esta dentro o fuera de un polígono. Se da la función main, 4 polígonos y 5 puntos a testear.
Existen muchas soluciones a este problema, pero el objetivo es que cada uno proponga su algoritmo propio.
Cualquier duda se puede colgar en el hilo, y la solución se debe adjuntar en un archivo con la misma estructura que el original para que otros usuarios lo puedan probar cómodamente.

¿Premio? El ganador recibirá una INCREÍBLE, FANTÁSTICA e INOLVIDABLE postal de www.postales.com ...jeje

El código original:

Código: C

1. #include        <stdlib.h>
2. #include        <stdio.h>
3. #include        <math.h>
4.  
5.  
6. #define FUERA   0
7. #define DENTRO  1
8. #define POLIGONOS_TEST_MAX      4
9. #define PUNTOS_TEST_MAX         5
10. #define LINEAS_POR_POLIGONO     12
11.  
12.  
13. typedef struct{
14.         float X;
15.         float Y;
16. }Punto;
17.  
18. typedef struct{
19.         Punto P0, P1;
20. }Linea;
21.  
22. typedef struct{
23.         char nombre[5];
24.         int size;
25.         Linea lineas[LINEAS_POR_POLIGONO];
26. }Poligono;
27.  
28. const Poligono poligonos_test[POLIGONOS_TEST_MAX] = {
29.                         {"Tria", 3, {
30.                                         {{0,0},{3,7}}, {{3,7},{6,0}}, {{6,0},{0,0}}, {{0,0},{0,0}},
31.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
32.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
33.                                 }
34.                         },
35.                         {"Rect", 4, {
36.                                         {{0,0},{0,7}}, {{0,7},{7,7}}, {{7,7},{7,0}}, {{7,0},{0,0}},
37.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
38.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
39.                                 }
40.                         },
41.                         {"Letr", 12, {
42.                                         {{0,0},{0,7}}, {{0,7},{1,7}}, {{1,7},{3,5}}, {{3,5},{5,7}},
43.                                         {{5,7},{6,7}}, {{6,7},{6,0}}, {{6,0},{5,0}}, {{5,0},{5,5}},
44.                                         {{5,5},{3,3}}, {{3,3},{1,5}}, {{1,5},{1,0}}, {{1,0},{0,0}}
45.                                 }
46.                         },
47.                         {"Cora", 12, {
48.                                         {{0,3},{0,5}}, {{0,5},{1,6}}, {{1,6},{2,6}}, {{2,6},{4,4}},
49.                                         {{4,4},{3,3}}, {{3,3},{2,4}}, {{2,4},{4,6}}, {{4,6},{5,6}},
50.                                         {{5,6},{6,5}}, {{6,5},{6,3}}, {{6,3},{3,0}}, {{3,0},{0,3}}
51.                                 }
52.                         }
53.         };
54.  
55. const Punto puntos_test[PUNTOS_TEST_MAX] = {
56.                 {0,0}, {3,4}, {2,6}, {3,6}, {4,6}
57. };
58.  
59. int algoritmo( const Poligono plgn, const Punto pnt ){
60.         int resultado = 0;
61.  
62.         //      Implementacion del algoritmo. Resultado = DENTRO/FUERA
63.  
64.         return resultado;
65. }
66.  
67. int main(){
68.  
69.         int i, j;
70.  
71.         printf("www.TODOPIC.com.ar\n");
72.         printf("Concurso de programacion en C.\n");
73.         printf("Nombre del concursante: XXXX");
74.  
75.         for( i = 0 ; i < POLIGONOS_TEST_MAX ; i++ ){
76.  
77.                 printf( "\n\nTest del poligono %s...", poligonos_test[i].nombre );
78.  
79.                 for( j = 0 ; j < PUNTOS_TEST_MAX ; j++ ){
80.  
81.                         if( DENTRO == algoritmo( poligonos_test[i], puntos_test[j] ) )
82.                                 printf( "\nEl punto { %2.1f, %2.1f } se encuentra DENTRO", puntos_test[j].X,puntos_test[j].Y );
83.                         else
84.                                 printf( "\nEl punto { %2.1f, %2.1f } se encuentra FUERA", puntos_test[j].X,puntos_test[j].Y );
85.  
86.                 }
87.         }
88.  
89.         printf("\n\nTest terminado.");
90.         return 0;
91. }

Las figuras y los puntos a testear.

[micro_cadaver]

[x-logan]

Bueno yo me apunto a este miniconcurso, solo tengo unas preguntas/comentarios:
1.- Como vas a determinar quien gana, sera el algoritmo que se tarde menos o el que lo entregue primero o el mejor estructurado o cuales serian los criterios a calificar.
2.- Creo que seria mejor enviar por PM la respuesta y cuando se de por terminado la fecha limite para enviar la respuesta, se evalúan los algoritmos y una vez que se haya determinado un ganador pues ya se cuelgan todos en un post.

Espero tus comentarios.

salu2

[jgpeiro06]

Como vas a determinar quien gana

Gana el primero que implemente un algoritmo que funcione correctamente. Se puede imponer cualquier otro criterio, pero todo depende de cuanta gente participe(por el momento solo tu).

Creo que seria mejor enviar por PM

No creo que nadie tenga ningún motivo para hacer trampas. Quiero decir, el objetivo del concurso es que la gente se entretenga un poco desarrollando el algoritmo, no ganar la postal de felicitación...Si los concursantes ADJUNTAN la solución en el propio hilo otras personas que no quieran participar pueden consultar los algoritmos.

[Nocturno]

Sí, por favor, publicad los algoritmos a la vista de todos.
Yo no voy a participar porque me resulta imposible sacar tiempo, pero me muerdo las uñas por ver el algoritmo que funcione.

[LoPiTaL]

Yo también me apunto va. Se me ha metido la mosca en la oreja y me pasé toda la noche dándole vueltas... xDD aunque no he llegado a ninguna parte...

Un saludo,
LoPiTaL

[migsantiago]

Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho? 

[Nocturno]

Después de ver lo que ha hecho con el reloj Casio mediante FreeRTOS seguro que este algoritmo se lo papea en un rato.
Además, hay muchas versiones del mismo publicadas en Internet, por lo que dudo que se lo hayan puesto como tarea.

Lo divertido realmente es inventarse un método.

[migsantiago]

OOhhh 

A mi se me ocurre uno pero lo intentaría hasta el fin de semana. ¿Hasta cuándo podemos participar? 

[jgpeiro06]

Sí, por favor, publicad los algoritmos a la vista de todos.

Ok. Las posibles soluciones serán enviadas en un archivo adjunto con el formato del main.c original.

Se me ha metido la mosca en la oreja y me pasé toda la noche dándole vueltas...

Para mi resulto interesante porque es muy fácil determinar que puntos están dentro del polígono echando un simple vistazo. Pero aun siendo tan evidente que puntos están dentro o fuera, uno no sabe nada sobre que ha echo el cerebro para saberlo. Cuando intentas implementar el algoritmo te das cuenta de que es mas complejo de lo que parecía...

Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho?

Bueno, lo cierto es que no tengo la solución en mano. Me plantearon este reto hace 3 años y estuve unas semanas escribiendo programas hasta que la encontré, pero tengo que reconocer que no se donde estará el código. De todas maneras creo que podría volverlo a implementar.
Desde luego si necesitase este algoritmo lo buscaría en internet antes de inventarme esto como excusa.

[MLO__]

Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho? 

Creo que mig estaba chanceando unicamente .... molestando ..... tomando el pelo ... 

Esta muy interesante ... pero yo si que soy pesimo para programar, sin embargo estare muy pendiente de las soluciones.

[cerebro]

yo ya tengo una idea que no puede fallar.... aunque me falta tiempo y tengo las neuronas en agua fria, si alguien se me alia le paso un pseudocodigo...

[x-logan]

Gana el primero que implemente un algoritmo que funcione correctamente. Se puede imponer cualquier otro criterio, pero todo depende de cuanta gente participe(por el momento solo tu).

Ok, entonces el primero gana

otras personas que no quieran participar pueden consultar los algoritmos.

claro, habra muchos que no participen y aun asi puedan revisar los algoritmos.

ya lo he estado pensando pero no he tenido tiempo para codificarlo.

salu2

[jgpeiro06]

¿como van esos algoritmos?
¿alguien esta intentando resolver el problema?

Si alguno tiene una solución que funciona solo en algunos casos que la publique para darle vida al hilo,¿no?.

Saludos

[migsantiago]

jejeje no te desesperes es un trabajo difícil