Spegnete le luci (Platino)#10603
Il fattore John ha installato nella sua stalla una nuova mungitrice moderna, ma essa consuma così tanta energia elettrica che a volte causa interruzioni di corrente! Questo 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 le interruzioni di corrente influenzino la sua capacità di uscire rapidamente dalla stalla. Ad esempio, vuole capire quanto più lontano potrebbe dover camminare 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 ); 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 un certo vertice (x_i, y_i) per i > 1. Può muoversi solo lungo il perimetro della stalla — in senso orario o antiorario, cambiando direzione se necessario ogni volta che raggiunge un vertice. Il suo obiettivo è percorrere la distanza minima possibile per raggiungere l'uscita. Con le luci accese, ovviamente, è abbastanza semplice farlo: può muoversi dalla sua posizione attuale verso l'uscita sia in senso orario che antiorario, scegliendo il percorso più breve.
Un giorno le luci si spengono, e Bessie, nel panico, dimentica esattamente in quale vertice si trova. Fortunatamente, ricorda ancora perfettamente la mappa della stalla, quindi può cercare di determinare la propria posizione muovendosi lungo il perimetro e usando il tatto. Ogni volta che si trova in un vertice (incluso il vertice di partenza), può determinare se la svolta in quel vertice è a sinistra o a destra, e può anche sapere se quel vertice è l'uscita. Quando percorre un lato della stalla, può determinarne la lunghezza esatta dopo averlo completamente attraversato.
In generale, Bessie esplorerà strategicamente lo spazio circostante, partendo dal suo vertice, finché non avrà raccolto informazioni sufficienti per determinare esattamente dove si trova. Dopodiché, potrà facilmente determinare il modo più breve per raggiungere l'uscita, percorrendo la distanza minima rimanente possibile.
Aiuta Bessie a determinare l'incremento minimo possibile della distanza percorsa nel caso peggiore (su tutti i possibili vertici di partenza) muovendosi al buio rispetto a muoversi con le luci accese, supponendo che in ciascun caso utilizzi la strategia ottimale. Una strategia "ottimale" al buio è quella che minimizza questa distanza aggiuntiva nel caso peggiore.
La prima riga contiene un numero intero n~(4 \le n \le 200). Ciascuna delle successive righe contiene due numeri interi che descrivono i punti (x_i, y_i) nell'ordine in cui vengono percorsi in senso orario attorno alla stalla. Questi numeri interi sono compresi tra -10^5 e 10^5.
Stampa il valore minimo possibile nel caso peggiore, di quanto la distanza ottimale percorsa da Bessie al buio superi la distanza ottimale percorsa con le luci accese. Il caso peggiore viene considerato su tutti i possibili vertici in cui Bessie può iniziare a muoversi.
In questo esempio, Bessie può determinare di trovarsi inizialmente in un angolo interno. Tuttavia, poiché tutti gli angoli in questo esempio sono angoli interni, questa informazione le è di scarsa utilità.
Una delle strategie ottimali è semplicemente muoversi in senso orario. Questa strategia è ottimale se inizia a muoversi dal vertice o , e aggiunge solo unità di distanza se inizia a muoversi dal vertice .
Esempio 1