Don't like ads? PRO users don't see any ads ;-)
Guest

Algorithme milieux

By: a guest on Apr 28th, 2012  |  syntax: C  |  size: 1.87 KB  |  hits: 99  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #define MAX_POINTS 1000
  5.  
  6. typedef struct Coordonnees Coordonnees;
  7. struct Coordonnees
  8. {
  9. int x;
  10. int y;
  11. };
  12.  
  13. // Compare deux coordonées, d'abord selon l'abscisse puis si égalité selon l'ordonnée
  14. int plusPetit(const void* p1, const void* p2)
  15. {
  16. const Coordonnees *point1 = (const Coordonnees*)p1;
  17. const Coordonnees *point2 = (const Coordonnees*)p2;
  18. int diff = point1->x - point2->x;
  19.     if (diff != 0)  {return (diff);}
  20.     else {return (point1->y - point2->y);}
  21. }
  22.  
  23. int main()
  24. {
  25. Coordonnees point[MAX_POINTS];
  26. Coordonnees milieux[MAX_POINTS*MAX_POINTS];
  27. int nbPoints = 0;
  28. int nbMilieux = 0;
  29. int nbCorrespondance = 0;
  30. int x0 = 0;
  31. int y0 = 0;
  32. int i = 0;
  33. int j = 0;
  34. // Lecture des coordonnées
  35. scanf("%d", &nbPoints);
  36. for (i = 0; i < nbPoints; i++)
  37.    {
  38.    scanf("%d %d", &point[i].x, &point[i].y);
  39.    }
  40. // Calcul des milieux
  41. for (i = 0; i < nbPoints; i++)
  42.    {
  43.    for (j = 0; j < nbPoints; j++)
  44.       {
  45.       x0 = (point[i].x + point[j].x)%2;         //Le milieu n'est ajouté
  46.       y0 = (point[i].y + point[j].y)%2;         //que si ses coordonnées
  47.       if ( (i != j) && (x0 == 0) && (y0 == 0) ) //sont entieres, et que
  48.          {                                      //les 2 points sont distincs
  49.          milieux[nbMilieux].x = (((point[i].x + point[j].x))/2);
  50.          milieux[nbMilieux].y = (((point[i].y + point[j].y))/2);
  51.          nbMilieux++;
  52.          }
  53.       }
  54.    }
  55. // Tri des milieux en ordre croissant, pour effectuer des recherches ensuite
  56. qsort(milieux, nbMilieux,sizeof(milieux[0]), plusPetit);
  57. // Pour chaque point, je cherche si il appartient au tableau milieux
  58. for (i = 0; i < nbPoints; i++)
  59.    {
  60.    if (bsearch(&point[i], milieux, nbMilieux, sizeof(milieux[0]), plusPetit))
  61.    {nbCorrespondance++;}
  62.    }
  63.  
  64. // Affichage de la sortie
  65. printf("%d", nbCorrespondance);
  66. return(0);
  67. }