Si spegne la luce (Oro)#10600
Il contadino Giovanni ha installato nella sua stalla una nuova e moderna macchina per la mungitura, ma essa consuma così tanta energia elettrica che a volte provoca interruzioni di corrente! Ciò accade così spesso che Bessie ha imparato a memoria la mappa della stalla, il che le rende più facile trovare l'uscita dalla stalla al buio. Tuttavia, si chiede come l'interruzione di corrente influisca sulla sua capacità di lasciare rapidamente la stalla. Ad esempio, vuole capire di quanto potrebbe dover camminare in più al buio per trovare l'uscita.
La stalla è descritta da un poligono semplice (che non si autointerseca) con vertici a coordinate intere (x_1, y_1), \ldots, (x_n, y_n), elencati in senso orario. I suoi lati si alternano tra orizzontali (paralleli all'asse ) e verticali (paralleli all'asse ), e il primo lato può essere di uno dei due tipi. L'uscita si trova nel punto (x_1, y_1). Bessie inizia a muoversi all'interno della stalla, trovandosi in uno dei vertici (x_i, y_i) per i \gt 1. Può muoversi solo lungo il perimetro della stalla — in senso orario o antiorario. Il suo obiettivo è percorrere la minor distanza possibile per raggiungere l'uscita. Con la luce accesa, ovviamente, farlo è abbastanza semplice: può muoversi dalla sua posizione attuale verso l'uscita sia in senso orario che antiorario, scegliendo il percorso più breve.
Un giorno la luce si spegne, e Bessie, in preda al panico, dimentica esattamente in quale vertice si trovi. Fortunatamente, ricorda ancora esattamente la mappa della stalla, quindi può provare a determinare la propria posizione muovendosi lungo il perimetro e usando il tatto. Ogni volta che si trova in un vertice (compreso il vertice di partenza), può determinare l'esatto angolo interno di quel vertice, oltre a scoprire se quel vertice sia l'uscita. Quando percorre un lato della stalla, può determinarne la lunghezza esatta dopo averlo percorso interamente.
Bessie sceglie la seguente strategia: si muoverà in senso orario lungo il perimetro della stalla finché non avrà percepito abbastanza angoli e lati da poter determinare in modo univoco il vertice in cui si trova. Dopodiché potrà facilmente determinare il percorso più breve verso l'uscita: continuare a muoversi in senso orario oppure invertire la direzione e muoversi in senso antiorario.
Aiuta Bessie a determinare l'aumento massimo, nel caso peggiore (su tutti i possibili vertici di partenza), della distanza percorsa muovendosi al buio rispetto a quella percorsa muovendosi con la luce accesa.
La prima riga contiene un intero n~(4 \le n \le 200). Ciascuna delle successive righe contiene due interi che descrivono i punti (x_i, y_i) in ordine orario attorno alla stalla. Questi interi sono compresi nell'intervallo -10^5 \le x_i, y_i \le 10^5.
Stampa l'aumento massimo della distanza percorsa da Bessie nel caso peggiore su tutti i possibili vertici di partenza, utilizzando la strategia descritta nell'enunciato.
In questo esempio, Bessie può determinare di trovarsi inizialmente in un vertice con un angolo di gradi, ma non può capire se si trova nel vertice , o . Dopo aver percorso un lato in senso orario, raggiunge l'uscita oppure può determinare in modo univoco la propria posizione in base alla lunghezza di quel lato. Consideriamo le distanze che percorre:
Se Bessie inizia nel vertice , allora al buio percorre unità: unità per raggiungere il vertice , e poi altre unità per raggiungere l'uscita. Con la luce accesa, le basta percorrere unità. Quindi, per questo vertice di partenza, la distanza aggiuntiva è di unità.
Se Bessie inizia nel vertice , in entrambi i casi percorre unità.
Se Bessie inizia nel vertice , in entrambi i casi percorre unità.
Di conseguenza, la differenza nel caso peggiore su tutti i possibili vertici di partenza è pari a 12 - 10 = 2. In altre parole, Bessie può garantire che, indipendentemente da dove inizi, utilizzando la sua strategia al buio percorrerà non più di unità in più rispetto a quando la luce è accesa.
Esempio 1