# Art Gallery Selection

**URL:** <https://forum.olinfo.it/t/art-gallery-selection/5512>\
**Category:** Aiuto\
**Created:** [14 Gennaio 2019, 9:06pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512 "2019-01-14T21:06:29Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![simone00](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/ba9def/32.png) [@simone00](https://forum.olinfo.it/u/simone00)\
**Post date:** [14 Gennaio 2019, 9:06pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/1 "2019-01-14T21:06:29Z")

</div>

salve, ho un problema con l’algoritmo di risoluzione del seguente esercizio:

```auto
#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.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [15 Gennaio 2019, 12:41pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/2 "2019-01-15T12:41:34Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![simone00](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/ba9def/32.png) [@simone00](https://forum.olinfo.it/u/simone00)\
**Post date:** [15 Gennaio 2019, 1:05pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/3 "2019-01-15T13:05:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [15 Gennaio 2019, 3:06pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/4 "2019-01-15T15:06:00Z")

</div>

> [@simone00](#):
>
> 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).

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) 🤔 🤔 🤔

---

<div class="post-metadata">

**Author:** ![simone00](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/ba9def/32.png) [@simone00](https://forum.olinfo.it/u/simone00)\
**Post date:** [15 Gennaio 2019, 3:18pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/5 "2019-01-15T15:18:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [15 Gennaio 2019, 3:47pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/6 "2019-01-15T15:47:17Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![simone00](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/ba9def/32.png) [@simone00](https://forum.olinfo.it/u/simone00)\
**Post date:** [15 Gennaio 2019, 6:11pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/7 "2019-01-15T18:11:00Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [15 Gennaio 2019, 11:07pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/8 "2019-01-15T23:07:26Z")

</div>

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.

```auto
5
1 5
9 5
5 5
4 5
8 5

```

Qual è la risposta corretta? Qual è la risposta del tuo algoritmo? _Perché_ accade ciò?

---

<div class="post-metadata">

**Author:** ![simone00](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/ba9def/32.png) [@simone00](https://forum.olinfo.it/u/simone00)\
**Post date:** [16 Gennaio 2019, 12:46pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/9 "2019-01-16T12:46:29Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [16 Gennaio 2019, 1:02pm UTC](https://forum.olinfo.it/t/art-gallery-selection/5512/10 "2019-01-16T13:02:19Z")

</div>

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

> [@](#):
>
> help Luca determine whether there exists a vertical axis of symmetry **for the given points**

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.