Divisione del campo#10574
Tutte le mucche di Farmer John si trovano in punti distinti del suo campo bidimensionale. FJ vuole recintare tutte le mucche con una recinzione rettangolare, i cui lati siano paralleli agli assi e . Vuole che la recinzione sia il più piccola possibile, ma che contenga comunque tutte le mucche; le mucche possono trovarsi sul confine della recinzione.
Sfortunatamente, a causa della scarsa produzione di latte nell'ultimo trimestre, FJ sta attraversando difficoltà finanziarie. Pertanto vorrebbe ridurre l'area totale che deve recintare, e l'unico modo che gli viene in mente per farlo è costruire due recinzioni invece di una.
Aiuta FJ a determinare quanta area totale potrà risparmiare utilizzando due recinzioni invece di una. Come per la recinzione originale, le due nuove recinzioni insieme devono contenere tutte le mucche; le mucche possono trovarsi sui loro confini, e i lati di entrambe le recinzioni devono essere paralleli agli assi e . Le due recinzioni non devono intersecarsi, nemmeno lungo i loro confini.
Nota che sono ammesse recinzioni di area nulla. Ad esempio, una recinzione può avere larghezza e/o altezza pari a zero.
La prima riga contiene un numero intero n~(3 \le n \le 50000).
Le successive righe contengono ciascuna due numeri interi, che indicano le coordinate di una mucca. Le coordinate delle mucche sono numeri interi positivi compresi tra e 10^9.
Stampa un singolo numero intero — l'area totale che FJ potrà risparmiare utilizzando due recinzioni invece di una.
Esempio 1