Cod sursa(job #1149013)

Utilizator span7aRazvan span7a Data 21 martie 2014 13:30:41
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define M 2000000000
using namespace std;
FILE *f=fopen("popandai2.in","r");
FILE *g=fopen("popandai2.out","w");
struct coord
{
    int x,y;
    double tg;
};
coord L[1001];
double maxim=-1;
double arie;
int stiv[1001],n,minx=M,miny=M,sf;

int cmp(coord a,coord b)
{
    return a.tg>b.tg;
}
double det1(coord a,coord b,coord c)
{
    return abs((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
}
void muta(int &x,int &y)
{
    x=x-minx;
    y=y-miny;
}
void citire()
{
    int i,xx,yy,poz;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d%d",&xx,&yy);
        L[i].x=xx;
        L[i].y=yy;
        if(minx>xx)
        {
            minx=xx;miny=yy;poz=i;
        }
        else if(minx==xx)
                if(miny>yy){miny=yy;poz=i;}
    }
    for(i=poz;i<n;i++)L[i]=L[i+1];n--;
    for(i=1;i<=n;i++) muta(L[i].x,L[i].y);
    for(i=1;i<=n;i++) L[i].tg=atan2(L[i].y,L[i].x);
    sort(L+1,L+n+1,cmp);
}
int main()
{
    int i,j,k,l;
    citire();
    minx=-minx;miny=-miny;
    for(i=0;i<=n;i++)muta(L[i].x,L[i].y);
   for(i=0;i<=n-3;i++)
        for(j=i+1;j<=n-2;j++)
            for(k=j+1;k<=n-1;k++)
                for(l=k+1;l<=n;l++)
                    {
                        arie=(0.5)*(det1(L[i],L[j],L[k])+det1(L[i],L[k],L[l]));
                        maxim=max(maxim,arie);
                    }

    fprintf(g,"%.1lf",maxim);
    return 0;
}