Poslednjih nekoliko meseci, naš stari farmer Branko, videvši da se dosta farmera preselilo u grad, odlučio je da podeli svoju zemlju ostalim farmerima koji će vredno da rade na njoj, i time spreči da njegovo mestašce nestane.
Farmer Gojko, koji je živeo nedaleko od Brankovog poseda, je upravo saznao za ovu akciju. Požurio je i on da dobije neko parče zemlje, ali već je bilo kasno. Branko je već podelio skoro celu zemlju. Ostalo je samo jedno malo parče zemlje.
Iznenađen ovakvim razvojem situacije, farmer Branko je izmislio igru, kojom će podeliti ostatak svoje zemlje, tako da što više ljudi dobije svoje parče. Branko je postavio n (n ≤ 2000) stubića u zemlju. Onaj ko prvi dođe ima pravo da uzme bilo koje četvorougaono parče zemlje, čija su temena tamo gde se nalaze stubići. Pravila igre za one koji stignu kasnije su veoma komplikovana. Na vašu sreću, farmer Gojko je stigao prvi, i sada treba da izabere četiri stubića. Pomozite mu da izabere najbolja 4 stubića, tako da dobije zemlju najveće površine.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke farmeri.in.) U prvoj redu ulaza nalazi se broj n (4 ≤ n ≤ 2.000). U sledećih n redova nalaze se po dva mešovita (realna) broja - x i y koordinata jednog stubića (-200.000,0 ≤ x, y ≤ 200.000,0). U 50% test primera, n ≤ 200.

Izlaz.

(Izlazni podaci se ispisuju u datoteku farmeri.out.) U izlaznom fajlu trebate ispisati najveću površinu koju farmer Gojko može dobiti, zaokruženu na tri decimale.

Napomena. Nisu svi stubići kolinearni, tj rešenje će uvek biti veće od 0.

Primer 1.

6
0 0
0 1
1 0
1 1
0.5 0.5
1.5 1.5

1.500

Primetimo prvo da svaki četvorougao (i konveksni i ne konveksni) sadrži bar jednu svoju dijagonalu. Za neki par tačaka A i B, izračunaćemo tačke C i D, tako da je C sa leve, a D sa desne strane prave AB, i da trouglovi ABC i ABD imaju najveću moguću površinu. Tako da znamo, da od svih četvorouglova koji sadrže dijagonalu AB u sebi, najveća moguća površina je baš P(ACBD). Ako izračunamo P(ACBD) za svaki par tačaka A i B, najveći od tih brojeva je traženi rezultat.
Ako, za fiksirano A i B, prođemo kroz svaku tačku sa leve strane i tako izračunamo C, i slićno za D, složenost ovog rešenja je O(n³), što donosi 50 poena.
Ako primetimo da tačka C je najudaljenija od segmenta AB, znamo da ona mora biti jedna od tačaka sa konveksnog omotača. Neka su E₁, E₂ ... E_k tačke na konveksnom omotaču sa leve strane segmenta AB, i označimo sa H_i rastojanje tačke E_i do prave AB. Znamo da je P(ABE_i) = |AB| * Hi / 2. Takođe znamo da je H₁ < H₂ < ... < H_t > ... > H_k, i C = H_t. Tako da možemo binarnom pretragom naći tačku H_t. Složenost ovog rešenja je O(n² * log n), što donosi oko 80 poena.
Lako se vidi da samo jedna tačka najvećeg četvorougla ne mora biti na konveksnom omotaču (i to ako i samo ako se nalaze tačno tri tačke na konveksnom omotaču). Tako da možemo reći da to mora biti tačka A. Za svaku tačku A (i sa konvekson i one koje nisu), izračunaćemo najbolje tri tačke B, C i D na konveksnom omotaču. Neka su E₁, E₂ ... E_k tačke sa konveksnog omotača. Ako smo izračunali C = E_v i D = E_w, za neku tačku B = E_u, gde se mogu nalaziti tačke C i D, za B = E_{u + 1}? Ako povećamo v dok je H_v < H_{v + 1}, dobijamo baš novu tačku C = E_v, i na slični način dobijemo i D. Koja je složenost ovog algoritma. Primetimo da za jednu tačku A, i v i w mogu svaki broj proći tačno jednom, tako da je složenost O(n²). Ovo rešenje donosi 100 poena.

Očigledno rešenje u O(n⁴) donosi 10-20 poena.

Neko odvojeno može uraditi slučaj ako na konveksnom omotaču imaju tačno tri tačke, ali samo jedan primer ima slučaj da su tačno tri tačke na omotaču. Ali je sa ovim zapažanjem rešenje malo kraće i jednostavnije.
Ako postoje više od tri tačke na konveksnom omotaču, možemo posmatrati samo tačke sa omotača. Test primeri 5., 13. i 15. imaju malo tačaka na omotaču, pa ovo zapažanje donosi poene na ovim primerima.

Test primeri:
nom - broj na konveksnom omotaču

1.

4

3

2.

30

7

3.

50

50

4.

70

70

5.

100

14

6.

100

100

7.

130

130

8.

150

149

9.

200

166

10.

200

200

11.

300

257

12.

500

428

13.

700

232

14.

700

694

15.

2000

22

16.

2000

572

17.

1000

993

18.

1500

1480

19.

2000

816

20.

2000

1966

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

const int maxn=2000;
const double eps=1e-8;
const double infinite=1e30;
const double pi=3.141592653589; 

typedef struct
{ double x,y,angle;        
} point;

int n,noh,hull[maxn];
point p[maxn];



inline int different(int i,int j,int k=-1,int l=-2)
{
    return ( (i!=j) && (i!=k) && (i!=l) && (j!=k) && (j!=l) && (k!=l) );  
}



inline double area(int i,int j,int k,int l)
{
    double a=0;   
    a+=p[i].x*p[j].y-p[j].x*p[i].y;
    a+=p[j].x*p[k].y-p[k].x*p[j].y;    
    a+=p[k].x*p[l].y-p[l].x*p[k].y; 
    a+=p[l].x*p[i].y-p[i].x*p[l].y; 
    if (a<0) a=-a;   
    return a;       
}

inline double area(int i,int j,int k)
{
    double a=0;   
    a+=p[i].x*p[j].y-p[j].x*p[i].y;
    a+=p[j].x*p[k].y-p[k].x*p[j].y;    
    a+=p[k].x*p[i].y-p[i].x*p[k].y; 
    return a;       
}
int compare(const void *pa,const void *pb)
{
   point *a=(point*)pa,*b=(point*)pb;

  if ((a->angle)>(b->angle)) return 1;
  if ((a->angle)==(b->angle)) return 0;
  return -1;
}

int left(int a,int b,int j)
{
  double t=(p[b].x-p[a].x)*(p[j].y-p[a].y)-(p[b].y-p[a].y)*(p[j].x-p[a].x);
  if (t<-eps) return 1;
  if (t>eps) return -1; 
  return 0;
}

int main()
{
    int ts=clock();
    
    freopen("farmeri.in","r",stdin);
    freopen("farmeri.out","w",stdout);
        
    int i,j,k,l,nextl;
    double result,inter,bestleft,bestright;
    point pom;
        
    scanf("%d",&n);
    for(i=0;i<n;i++)
       scanf("%lf%lf",&(p[i].x),&(p[i].y));
 
 //------------------------
    p[0].angle=0;
    k=0;

    for(i=1;i<n;i++)
    {
      p[i].angle=0;
      if ( (p[k].y>p[i].y) || (((p[i].y-p[k].y)<eps)&&(p[k].x<p[i].x)) )
       k=i;
    }

    pom=p[0];p[0]=p[k];p[k]=pom;

    for(i=1;i<n;i++)
    {
       p[i].x-=p[0].x;
       p[i].y-=p[0].y;
       p[i].angle=atan2(p[i].y,p[i].x);
       if (p[i].angle<0) p[i].angle+=2*pi;
    }

    p[0].x=0;p[0].y=0;p[0].angle=0;

    qsort(p,n,sizeof(point),compare);

    hull[0]=0;hull[1]=1;
    k=1;
  
  
    for(i=2;i<n;i++)
    {
       while ((k>=1) && (left(hull[k-1],hull[k],i)==1)) k--;
       k++;
       hull[k]=i;                    
    }

    while ((k>=1) && (left(hull[k-1],hull[k],hull[0])==1)) k--;

    k++;
 
    noh=k;
    
    result=-infinite;     
    if (noh>3)    
       for(i=0;i<noh;i++)
       {
          k=i+1;l=(i+3)%noh;
          for(j=i+2;j<noh;j++)
          {
             while (area(hull[i],hull[k],hull[j])<area(hull[i],hull[k+1],hull[j])) k++;
             nextl=(l+1)%noh;
             while (area(hull[i],hull[j],hull[l])<area(hull[i],hull[j],hull[nextl]))
                {l=nextl;nextl=(l+1)%noh;}                                   
             inter=area(hull[i],hull[k],hull[j])+area(hull[i],hull[j],hull[l]);
             if (inter>result) result=inter;                          
          }
       }
    else 
       for(i=0;i<n;i++)
          if (different(hull[0],hull[1],hull[2],i)) 
          {
             inter=area(hull[0],hull[1],hull[2],i);
             if (inter>result) result=inter;
             inter=area(hull[0],hull[1],i,hull[2]);
             if (inter>result) result=inter;
             inter=area(hull[0],i,hull[1],hull[2]);
             if (inter>result) result=inter;                                                                          
          }
           
    printf("%.3lf\n",result / 2);
    
    return 0;    
}