Riduzione del campo (Argento)#10571
Tutte le mucche del fattore John si trovano in punti distinti del suo campo bidimensionale. FJ vuole recintare tutte le sue mucche con uno steccato rettangolare, i cui lati sono paralleli agli assi e . Vuole che lo steccato sia il più piccolo possibile, ma che allo stesso tempo contenga tutte le mucche; le mucche possono trovarsi direttamente sul confine dello steccato.
Sfortunatamente, a causa della scarsa produzione di latte nell'ultimo trimestre, FJ sta attraversando difficoltà finanziarie. Perciò vorrebbe, se possibile, rendere il territorio recintato ancora più piccolo ed è disposto a vendere fino a tre mucche dalla sua mandria per riuscirci.
Aiuta FJ a determinare l'area minima possibile che potrà recintare dopo aver rimosso dalla mandria non più di tre mucche e aver poi costruito il rettangolo più piccolo possibile che contenga tutte le mucche rimanenti.
In questo problema considera le mucche come punti, e lo steccato come quattro segmenti (cioè non considerare le mucche come "quadrati unitari"). Nota che la risposta può essere pari a zero; questo accade, per esempio, se tutte le mucche rimanenti giacciono su una stessa retta verticale o orizzontale.
La prima riga contiene un numero intero n~(5 \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 potrà recintare dopo aver rimosso non più di tre mucche, scelte in modo ottimale.
Esempio 1