PROBLEMA Programma in c per 2 punti equidistanti

[Utahraptor]

Salve a tutti volevo chiedere se qualcuno potesse fornirmi un codice (in c) per risolvere questo esercizio:
Dati N punti nel piano (vengono forniti un vettore X con le ascisse ed un vettore Y con le ordinate e ovviamente il numero N) dire se ci sono coppie di punti equidistanti (basta trovare una coppia non serve specificare quale o andare avanti con il programma una volta trovata). Con coppie equidistanti si intendono ad esempio i punti A e D che distano 10m e i punti F e G che distano anche loro 10m.

 

[rctimelines]

Vuoi proprio il codice per esteso?

Inviato dal mio Nexus 6P utilizzando Tapatalk

 

[_Achille]

Certo, ecco qui:

#include <stdio.h>
#include "points.h"

int main() {
    solveProblem();

    return 0;
}

 

[rctimelines]

Si appunto, perché come puoi immaginare, siamo tutti qui frementi di sapere come fare per evitare che tu ti stanchi troppo!

Inviato dal mio Nexus 6P utilizzando Tapatalk

 

[Andretti60]

Su ragazzi siate gentili, si è appena iscritto

Regolamento

 

[theprogrammer.99]

Su ragazzi siate gentili, si è appena iscritto

Regolamento

Mi sembra che siano stati estremamente gentili....

 

[rctimelines]

Peccato.. questo algoritmo era davvero una cazzata!

Inviato dal mio Nexus 6P utilizzando Tapatalk

 

[Mursey]

@Utahraptor segui il regolamento altrimenti si chiude.

 

[Utahraptor]

Scusate non ho ricevuto le notifiche delle risposte.
Ho voluto scrivere la domanda più semplice possibile in realtà il codice già l'ho fatto ma sono indeciso su quale sia il processo più efficace.
In entrambe i metodi viene creata una funzione "int DistanzaQuadrata" che presi in input 4 valori interi(le due ascisse e le due ordinate dei due punti) restituisce la distanza al quadrato sfruttando pitagora. Ed inoltre inizializzo tutto a -1 un vettore int d[] ,di dimensione (n*(n-1))/2 ovvero le possibili combinazioni delle distanze. Poi viene il dubbio
Primo metodo: calcolo una distanza, la inserisco nel vettore e controllo che non sia uguale ad una già inserita così in caso positivo posso interrompere il programma senza dover calcolare tutte le distanze.
Secondo metodo: calcolo tutte le distanze e le inserisco nel vettore, poi ordino il vettore usando il merge sort e infine controllo se ci sono valori uguali adiacenti.
La domanda è quindi qual è tra questi due l'algoritmo più efficiente, o se si può far di meglio.
Grazie a tutti

 

[_Achille]

Non stai usando C++ vero?
In tal caso ti basterebbe utilizzare std::set e std::set.contains() per vedere se hai già presente…

Comunque direi il secondo

 

[rctimelines]

Scusate non ho ricevuto le notifiche delle risposte.
Ho voluto scrivere la domanda più semplice possibile in realtà il codice già l'ho fatto ma sono indeciso su quale sia il processo più efficace.
In entrambe i metodi viene creata una funzione "int DistanzaQuadrata" che presi in input 4 valori interi(le due ascisse e le due ordinate dei due punti) restituisce la distanza al quadrato sfruttando pitagora. Ed inoltre inizializzo tutto a -1 un vettore int d[] ,di dimensione (n*(n-1))/2 ovvero le possibili combinazioni delle distanze. Poi viene il dubbio
Primo metodo: calcolo una distanza, la inserisco nel vettore e controllo che non sia uguale ad una già inserita così in caso positivo posso interrompere il programma senza dover calcolare tutte le distanze.
Secondo metodo: calcolo tutte le distanze e le inserisco nel vettore, poi ordino il vettore usando il merge sort e infine controllo se ci sono valori uguali adiacenti.
La domanda è quindi qual è tra questi due l'algoritmo più efficiente, o se si può far di meglio.
Grazie a tutti

Non serve fare quadrati e radici: due punti sono a uguale distanza se sono uguali le differenze tra le loro coordinate cioè hanno uguali delta-x e delta-y. Semplificando Pitagora infatti, è sufficiente che siano uguali i radicandi.

In pratica il controllo diventa estremamente veloce essendo un semplice confronto tra differenze.

Per fare il programma devi impostare due cicli annidati che confrontano le coordinate di ogni elemento dell'array con tutti quelli successivi. Esci appena ne trova una.

Inviato dal mio Nexus 6P utilizzando Tapatalk

 

[Utahraptor]

Ma scusa così i confronti da fare raddoppiano rispetto a pitagora

 

[rctimelines]

Ma scusa così i confronti da fare raddoppiano rispetto a pitagora

Ti risparmi due elevazioni al quadrato e una radice!!!! Non c'è termine di paragone.

Considera che il confronto, per una CPU è praticamente tra le operazioni più semplici (e veloci) che esegue.

Inviato dal mio Nexus 6P utilizzando Tapatalk

 

[Andretti60]

Non serve fare quadrati e radici: due punti sono a uguale distanza se sono uguali le differenze tra le loro coordinate cioè hanno uguali delta-x e delta-y.

Stai scherzando vero?
Hint: guarda le proprietà dei triangoli inscritti in un semicerchio.

 

[rctimelines]

Stai scherzando vero?
Hint: guarda le proprietà dei triangoli inscritti in un semicerchio.

La distanza tra due punti:

Radice della somma dei quadrati dei cateti

I cateti sono la differenza delle ascisse e la differenza delle ordinate

Limiti il confronto alle basi.

Magari sbaglio.. dove?

Inviato dal mio Nexus 6P utilizzando Tapatalk