Art Gallery Selection


#1

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.


#2

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.


#3

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


#4

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) :thinking: :thinking: :thinking:


#5

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


#6

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…


#7

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…


#8

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ò?


#9

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)


#10

Ecco! Adesso capisco perché non ci capiamo: c’è un’incomprensione di fondo rispetto al testo :joy:

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.