Riduzione del campo (Bronzo)#10570
Tutte le mucche del fattore Giovanni si trovano in punti distinti del suo campo bidimensionale. FJ vuole recintare tutte le sue mucche con una recinzione rettangolare, i cui lati sono paralleli agli assi e . La recinzione deve essere quanto più piccola possibile, ma deve comunque contenere tutte le mucche; le mucche possono trovarsi direttamente sul confine.
Sfortunatamente, a causa della scarsa produttività di latte nell'ultimo trimestre, FJ è costretto a risparmiare. Perciò vorrebbe, se possibile, rendere ancora più piccola l'area recintata, ed è disposto a vendere una mucca dalla sua mandria per riuscirci.
Aiuta FJ a determinare l'area minima possibile che potrà recintare dopo aver rimosso una mucca dalla mandria, e poi aver costruito il rettangolo delimitante minimo per le restanti n - 1 mucche.
In questo problema, considera le mucche come punti, e la recinzione come un insieme di quattro segmenti (cioè non considerare le mucche come "quadrati di lato 1"). Nota che la risposta può essere pari a zero; ciò accade, ad esempio, se tutte le mucche rimanenti giacciono su un'unica retta verticale o orizzontale.
Infine, poiché può essere piuttosto grande, è necessario scegliere con attenzione l'algoritmo affinché il programma funzioni abbastanza velocemente.
Nella prima riga si trova un numero intero n~(3 \le n \le 50000). Le successive righe contengono due numeri interi ciascuna, che indicano le coordinate di una mucca. Le coordinate delle mucche sono numeri interi positivi compresi tra e .
Stampa un singolo numero intero — l'area minima che FJ può recintare dopo aver rimosso una mucca appositamente scelta.
Esempio 1