Cod sursa(job #1150808)

Utilizator span7aRazvan span7a Data 23 martie 2014 16:03:18
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define M 2000000000
using namespace std;
FILE *f=fopen("rubarba.in","r");
FILE *g=fopen("rubarba.out","w");
struct coord
{
    int x,y;
    double tg;
};
coord L[200001];
int minx=M,miny=M;
int stiv[200001],n,sf;
coord aux;
int cmp(coord a,coord b)
{
    return a.tg>b.tg;
}
void muta(int &x,int &y)
{
    x=x-minx;
    y=y-miny;
}
void citire()
{   int i,poz;
    int xx,yy;
    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;
                }
    }
    swap(L[n],L[poz]);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 det(coord a,coord b,coord c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
void infasuratoare()
{

    int i;
    stiv[1]=1;sf=1;
    for(i=2;i<=n;i++)
    {
        while(sf>=1&&det(L[stiv[sf-1]],L[i],L[stiv[sf]])<0)sf--;
        stiv[++sf]=i;
    }
    minx=-minx;miny=-miny;
    for(i=0;i<=n;i++)muta(L[i].x,L[i].y);
}
void afisare()
{   int i;
    fprintf(g,"%d\n",sf+1);
    minx=-minx;miny=-miny;
    for(i=0;i<=n;i++)muta(L[i].x,L[i].y);
    for(i=sf;i>=0;i--)
        fprintf(g,"%d %d\n",L[stiv[i]].x,L[stiv[i]].y);
}
double dist(int x1,int y1,double a,double b,double c)
{
    return abs(a*x1+b*y1+c)/sqrt(a*a+b*b);
}
coord cauta(double a,double b,double c,double &dis)
{
    double auxx;
    double distmax=-M;
    int punct;
    int i;
    for(i=0;i<=sf;i++)
    {
        auxx=dist(L[stiv[i]].x,L[stiv[i]].y,a,b,c);
        if(auxx>distmax)
        {
            distmax=auxx;
            punct=i;
        }
    }
    dis=distmax;
    return L[punct];
}
void dreapta(double &a,double &b,double &c)
{
    double m;
    if (a != 0)
    {
        m = ((double)b)/a;
        a = m;
        b = -1;
        c = -m*aux.x + aux.y;
    }
    else
    {
        a = 1;
        b = 0;
        c = -aux.x;
    }
}
void solve()
{

    int i,x1,y1,x2,y2,punct;
    double a,b,c,a1,b1,c1;
    double minim=M;
    double lat1,lat2;
    double m;
    stiv[sf+1]=stiv[0];
    for(i=0;i<sf;i++)
    {
    x1=L[stiv[i]].x;x2=L[stiv[i+1]].x;
    y1=L[stiv[i]].y;y2=L[stiv[i+1]].y;
    a=x2-x1;
    b=y2-y1;
    c=y1*x2-x1*y2;
    punct=0;
    aux=cauta(a,b,c,lat1);
    a1=a;b1=b;c1=c;
    dreapta(a,b,c);
    aux=cauta(a,b,c,lat2);
    dreapta(a1,b1,c1);
    aux=cauta(a1,b1,c1,lat2);
    minim=min(minim,lat2*lat1);
    }
    fprintf(g,"%.2lf",minim);
}
int main()
{
    citire();
    infasuratoare();
    //afisare();
    solve();

    return 0;
}