Bonjour,

Je suis en train de faire un exercice sur le site France IOI, j'ai crée un algorithme qui répond au problème mais il n'est pas assez rapide.

Voilà ma solution : http://pastebin.com/dnYptmrV

Ce que doit faire le programme :
"On considère N points dans le plan. On souhaite déterminer le nombre de ces points qui sont situés exactement au milieu de deux autres. Les points ont des coordonnées entières et sont tous situés dans un carré dont les coins sont les points (0,0) et (100, 100), bords inclus.

En entrée :
Sur la première ligne, un entier N, représentant le nombre de points.
Chacune des N lignes suivantes contient deux entiers Xi et Yi séparés par un espace : les coordonnées d'un point.
En sortie :
Le nombre de points qui sont les milieux de 2 autres points. "

J'ai le droit à 16Mo de mémoire et à 0.25s dans le pire des cas.
Le pire des cas : il y a 1 000 points et 1 000 000 milieux.

Voilà comment marche mon algo :

Je lis les coordonnées des points dans un tableau.
Je calcule les coordonnées de tous les milieux dans un autre tableau.
je trie les coordonnées des milieux (avec qsort() )
pour chaque point du tableau de points, je regarde si ses coordonnées sont aussi dans le tableau de milieux (avec bsearch()recherche dichotomique ), si c'est le cas j’incrémente un compteur.
J'affiche le compteur.

D'après mes calculs j'utilise au pire 8,002 Mo de mémoire.
Et la complexité de mon algo est en O(n*log(n²)), car au pire j’effectue n fois une recherche dichotomique dans un tableau de n² valeurs.

Voilà j'espère que quelqu'un pourra me donner un conseil pour simplifier mon algorithme. Merci d'avance.

bonjour a toi.

Qu'est ce que ca veut dire etre au milieu de deux points dans un espace 2d? Est ce que ca veut dire etre dans le rectangle defini par ces deux points?

Je pense que tu as mal calculer la complexite de ton algorithme. Mais pour le rendre plus rapide, il ne faut pas traiter les points un par un.

Le point (x3,y3) est le milieu de (x2,y2) et (x1,y1) si x3 = (x1+x2)/2 et si y3 = (y1+y2)/2

C'est la première fois que j'essai de calculer la complexité d'un algorithme donc peux être que je me suis effectivement trompé.

Et pour vérifier plusieurs points en même temps je ne vois pas comment faire.

Oh, au milieu de cette facon!

relis l'enonce avec mon emphase.

"Les points ont des coordonnées ENTIERES et sont tous situés dans un carré dont les coins sont les points (0,0) et (100, 100)"

Ou meme plus precisement:

"Les points ont des coordonnées *entieres* et sont tous situés dans un carré dont les coins sont les points (0,0) et *(100, 100)*"

J'ai un algorithme en O(n) pour le preprocessing et O(1) pour le calcul.

En fait c'est juste que le repère où sont placés les points est le carré dont les coins sont les points (0,0) et (100, 100)

Oublie mon dernier message.

Donc déjà il existe un algo très rapide pour résoudre le problème, tu me rassures. Par contre je ne vois pas lequel, même en relisant le sujet et en insistant sur le fait que les coordonnées sont entières. Tu pourrais m'en dire plus ? Est-ce itératif ou récursif ? Est-ce que je dois lire toutes les entrées avant de commencer à compter ?

si l'entree est

(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)
(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)(0,0)
(0,0)(0,0)(0,0)(0,0)

(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)
(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)(6,6)
(6,6)(6,6)(6,6)(6,6)

(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)
(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)(3,3)
(3,3)(3,3)(3,3)(3,3)

combien de temps il te faut pour repondre au probleme?

si 2 points ont les mêmes coordonnées ils comptent pour un seul point, donc dans ce cas il me suffit de comparer le milieu de (6;6) et de (0;0) (car c'est le seul milieu dont les coordonnées sont un entier) à (3;3) et la réponse est 1.

C'est bon en réfléchissant un peu j'ai trouvé une méthode assez rapide pour passer les tests :

-J'initialise un tableau char points[101][101] à '.'
-J'initialise un tableau char pointsMilieux[101][101] à '.'
-Pour chaque point donné en entrée points[x][y] vaut 'P'
- Pour chaque couple de points possibles, si le milieu de ces 2 points a ses coordonnées entières, pointsMilieux[(x1+x2/2)][(x2+y2)/2] vaut 'M'
- Ensuite je parcours toute les cases de points, et si
points[x][y] == 'P' et pointsMilieux[x][y] == 'M', j’incrémente un compteur.

Bien!
Quel est la complexite de cet algorithme?

O(n²) je crois (le calcul de tous les milieux possibles avec n le nombre de points)

combien tu as de point au plus?

1000 points au plus (tous différents)

Si tu as 1000 points au plus, quelle est la complexite?

O(1000000) non ? J’exécute 1 millions de fois la boucle qui calcule le milieu.

et O(1000000) = O(1)

Apres lecture des donnees qui coute O(n) le reste des calculs coutent O(1)

Je ne comprend pas trop pourquoi on néglige le reste des calculs devant la lecture des données, alors que dans tous les cas c'est le reste des calculs le plus long. Le calcul des milieux dépend de n donc pourquoi on le considère comme une constante ?

Si n est le nombre de points alors la complexité de l'algorithme est O(n²), non ?

Aldebran, non, la complexite de l'algorithme est O(n) + O(1).

L'algorithme peut s'ecrire de la facon suivante.

int Matrix[100][100]
for all point (x,y); Matrix[x][y] = 1;

for i1 \in [0;100]; for j1 \in [0;100];
for i2 \in [0;100]; for j2 \in [0;100];
count +=
Matrix[i1][j1]*Matrix[i2][j2]*Matrix[(i1+i2)/2][(j
1+j2)/2]

return count;

J'ignore ici la question des milieux qui tombe sur des coordonnes non entiere qui ne change rien a la complexite du probleme. La multiplication est juste une ecriture inteligente de si il y a un point a (i1,j1) et a (i2,j2) et a ((i1+i2)/2,(j1+j2)/2).

La premiere boucle "for all point", a clairement un cout de O(n). La deuxieme a un cout constant de 100x100x100x100x3 access en memoire et 100x100x100x100x5 operations arithmetique. Donc O(1).

Ici, j'exploite le fait que l'enonce du probleme fixe la taille de l'espace qui contient tous les points. Si cet espace etait de taille variable (X,Y), alors la complexite de l'algorithme serait O(n) + O(X^2 Y^2).

Notons qu'en fonction de X,Y et n, l'algorithme propose par OP originalement pourrait etre plus rapide.