Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

ORDINAMENTO RETTANGOLI: TRANSITIVITA'

michelescara (1330 points)
1 2 6
in HW6 obbligatorio by (1.3k points)
Ciao a tutti, sto cercando di risolvere un problema sull'ordinamento dei rettangoli. Sono riuscito a salvare ogni rettangolo in una classe Rectangle e ho definito l'operatore > per stabilire se un rettangolo sovrappone un altro, in modo tale da ordinarli facilmente in una lista tramite sorted. Il problema si pone quando due rettangoli non si intersecano tra loro e hanno lo stesso numero di intersezioni ma con altri rettangoli. In questo caso il mio algoritmo non riconosce quale rettangolo è stato disegnato prima. So che dovrei implementare un algoritmo che si basa sulla transitività, ma non mi viene in mente un modo per farlo. Qualche consiglio? Dovrei continuare su questa strada o cambiare completamente approccio?
537 views
closed

4 Answers

Best answer
T
Tobia (1580 points)
1 12 19
by (1.6k points)
selected by
Inizialmente ci avevo provato anche io e sono incappato nello stesso problema, per risolverlo avevo creato una clausola nella definizione di minore che si attivava se i due triangoli erano inconfrontabili. in poche parole quello che facevo in questo caso è andare a trovare un  terzo rettangolo che intersecava entrambi i rettangoli che volevo confrontare e in base a quello vedeva quale dei due veniva prima. Purtroppo anche così perdi molti casi, alla fine ho concluso che il lavoro da fare per controllare tutto sarebbe stato troppo problematico e ho cambiato approccio.
michelescara (1330 points)
1 2 6
by (1.3k points)
edited by
Come hai fatto a prendere in esame il terzo rettangolo? È proprio quello che non riesco a fare. Molto probabilmente cambierò approccio, ma volevo fare un ultimo tentativo
T
Tobia (1580 points)
1 12 19
by (1.6k points)
cercavo un terzo rettangolo che aveva i due rettangoli come intersezioni esaminando tutte le intersezioni; trovato questo richiamavo la funzione < tra il primo e il terzo rettangolo e poi tra il secondo e il terzo, se uno veniva True e l'altro False allora trovavo l'ordinamento, ma fatto tutto questo il miglioramento riportato era praticamente nullo, quindi come ho già detto ho deciso di cambiare approccio
twgever (17470 points)
8 29 105
by (17.5k points)
Potresti costruirti una lista con i rettangoli ordinati.
[rosso,blu,giallo,verde,....,marrone] o simile. La lista te la puoi costruire confrontando i quadrati confrontabili a due a due. Semmai dovessi riuscirci, staresti a cavallo, perchè ti basta vedere dove si trova il rettangolo nella lista per capire come sta in relazione con gli altri. Il problema è farlo chiaramente, devi riuscire a salvarti dai casi particolari. Se il primo rettangolo sta sotto all'ultimo messo, devi far si che non appaia accanto all'ultimo, ma che rimanga il primo. Se questo dovesse risultare troppo difficile o impossibile, sarebbe meglio cambiare approccio.
l
luca.ronca (600 points)
0 0 5
by (600 points)
Un approccio è costruirsi una relazione formata da coppie (a, b) dove a < b, trovare la chiusura transitiva di quella relazione e poi ordinare con "sorted" più operator overloading di "<" ">" come stai facendo. Trovare la chiusura transitiva è il punto.
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
Anche io inizialmente ho provato così, ma poi ho dovuto cambiare algoritmo :)
Romitoskj (8920 points)
5 8 40
by (8.9k points)
Anche io... Sicuramente è fattibile ma inutilmente complicato.