salve, ho un problema con l’algoritmo di risoluzione del seguente esercizio:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <ctime>
bool is_vertical_axis(std::vector<std::pair<float,float>> points,int &dist)
{
std::vector<std::pair<float,float>> same_y;
for(int i = dist; (points[dist].second == points[i].second) && i < points.size(); i++)
same_y.push_back(points[i]);
std::vector<std::pair<float,float>> c_pairs;
for(int i = 0; i < same_y.size(); i++)
for(int j = i+1; j < same_y.size(); j++)
c_pairs.push_back(std::make_pair(same_y[i].first,same_y[j].first));
dist += same_y.size()-1;
for(int i = 0; i < c_pairs.size(); i++)
{
float axis = (c_pairs[i].first + c_pairs[i].second)/2.0f;
auto it = find_if(points.begin(),points.end(),[=](std::pair<float,float> a){return a.first == axis;});
if(it != points.end())
{
return true;
}
}
return false;
}
int main()
{
std::srand(std::time(0));
std::ifstream in("input.txt");
std::ofstream out("output.txt");
std::vector<std::pair<float,float>> points;
int N = 0;
in >> N;
points.resize(N);
for(int i = 0; i < N; i++)
{
in >> points[i].first >> points[i].second;
}
std::sort(points.begin(),points.end(),[](std::pair<float,float> a, std::pair<float,float> b)->bool{return a.second < b.second;});
for(int i = 0; i < N-1; i++)
{
if(points[i].second == points[i+1].second)
{
if(is_vertical_axis(points,i))
{
out << "YES";
in.close();
out.close();
return 0;
}
}
}
out << "NO";
in.close();
out.close();
return 0;
}
mi da 25 punti e non riesco a capire dove sbaglio.
Per prima cosa trovo tutti i punti aventi la stessa y e poi trovo tutte le possibili coppie e infine vedo se esiste un punto che possa essere l’asse.
Assumiamo per semplicità che le ordinate siano irrilevanti poiché uguali (come nei primi subtask).
A una prima rapida vista mi sembra che la funzione is_vertical_axis(p, i) controlli solo i punti da i in poi (rispetto all’elenco dei punti una volta ordinati). È vero che la invochi più volte (partendo da i=0), ma così facendo darebbe risposta positiva anche se solo gli ultimi n' punti sono simmetrici.
Se invece questa lettura è sbagliata, forse è opportuno che tu chiarisca maggiormente cosa fa il tuo codice.
Non credo che sia quello l’errore, perchè con la funzione find_if cerco l’ascissa dell’asse dall’inizio, fino alla fine(begin(), end()). Nel main, nel ciclo for in cui viene invocata la funzione is_vertical_axis(), è dichiarato un if che mi controlla se nell’array ordinato, chiamato points, esisterebbero dei punti con la stessa ordinata. Alla funzione is_vertacl_axis() vengono passati come parametri l’array di pair ordinato e la posizione in cui è stata ritrovata nell’array la coppia di valori con la stessa y. Nella funzione is_vertical_axis(), il primo ciclo for mi trova e mi salva in sames_v tutti i valori che hanno la stessa y(quindi nei primi subtask sames_v dovrebbe essere identico a points). Il secondo ciclo for mi salva in same_p tutte le possibili coppie di punti e prende in esame solo la loro x. L’ultimo ciclo for controlla se esiste un punto in points passante per l’asse. axis_x è il punto medio della coppia di punti esaminata e poi con find_if vede se esiste un valore che possa fungere da asse e, in caso, ritorna true.
spero di essere stato più chiaro. Grazie di tutto
Infatti proprio questo stavo contestando: la tua affermazione vale quando la funzione è chiamata con dist=0, ma non nelle chiamate successive con dist>0.
Peraltro il parametro dist della funzione è collegato alla i del main (che pare variare tra 0 e N), ma nella funzione sommi a dist il numero delle coppie (che è potenzialmente quadratico rispetto a N)
hai ragione, ma cambiando quell’errore, il risultato dei subtasks è rimasto più o meno invariato. A i gli ho aggiunto sames_v.size()-1. mi da corretto il subtask 4, mentre gli altri me li da sbagliati e corretti in modo alterno, tranne il 3 dove sono sbagliati il primo e l’ultimo
La logica della parte che contiene il find_if mi sembra scorretta. Presa una coppia, determini l’asse di simmetria per quella coppia; a quel punto, affinché tutto sia simmetrico, dev’essere che ogni altro punto:
cade esattamente sull’asse di simmetria
oppure
ha un “corrispondente” dall’altra parte dell’asse
Non mi sembra tu sia controllando questa seconda cosa, visto che verifichi solo l’esistenza di un punto che cade sull’asse…
nel testo dell’esercizio c’è scritto che i punti sono tutti distinti, e io trovo coppie di punti aventi la stessa y, ma che tra di loro sono distinsti, e poi con axis_x trovo “la x dell’asse”, e infine vedo se esiste con find_if. invece di avere l’asse e un punto, ho due punti che potrebbero essere simmetrici, credo che sia più efficiente(se il tutto funzionasse…).
il problema è che esiste un caso, che si ripete di frequente, che non fa funzionare pienamente il programma…
Insisto: la logica di fondo con cui verifichi in generale la simmetria di tutti i punti non va bene, non stai considerando il caso due del mio precedente commento.
Forse un esempio che ho costruito ad hoc ti può aiutare a ragionare.
5
1 5
9 5
5 5
4 5
8 5
Qual è la risposta corretta? Qual è la risposta del tuo algoritmo? Perché accade ciò?
la risposta del programma è YES e mi restituisce che il punto sull’asse è (5,5) mentre i punti simmetrici sono (1,5) e (9,5). Credo che sia la risposta corretta. ( ho modificato il primo messaggio che ho inviato con il programma che ho usato con l’esempio che mi hai fornito)
Ecco! Adesso capisco perché non ci capiamo: c’è un’incomprensione di fondo rispetto al testo
L’asse di simmetria, per esistere, deve essere asse per tutti i punti in input. Nell’esempio un tale asse non può esistere perché per i primi due punti sarebbe a x=5, mentre per gli ultimi due sarebbe a x=6.
