Cod sursa(job #917420)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 17 martie 2013 20:54:51
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#define INF 1e+18
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct punct
{
    int x,y;
};
int ccw(punct a,punct b,punct c)
{
    return((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
punct p[100009],LL;
bool cmp(punct a,punct b)
{
    if(ccw(LL,a,b)>0)
        return true;
    return false;
}
double lungime(punct a,punct b)
{
    return sqrt(((double)a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double arie(punct x,punct y,punct z)
{
    double a,b,c,per;
    a=lungime(x,y);
    b=lungime(y,z);
    c=lungime(x,z);
    per=((double)a+b+c)/2;
    return sqrt(per*(per-a)*(per-b)*(per-c));
}
double inaltime(punct c,punct a,punct b)
{
    // s=a*h/2 -> h=2*s/a
    return 2*arie(a,b,c)/lungime(a,b);
}
bool obtuz(punct a,punct b,punct c)
{
    if(lungime(a,b)*lungime(a,b)+lungime(b,c)*lungime(b,c)<lungime(a,c)*lungime(a,c)||
       lungime(a,b)*lungime(a,b)+lungime(a,c)*lungime(a,c)<lungime(b,c)*lungime(b,c))
       return true;
    return false;
}
int infasuratoare[100009];
int main()
{
    int i,n;
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d",&p[1].x,&p[1].y);
    LL.x=p[1].x;
    LL.y=p[1].y;
    int pozll=1;
    for(i=2;i<=n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        if(p[i].y<LL.y||(p[i].y==LL.y&&p[i].x<LL.x))
        {
            LL.x=p[i].x;
            LL.y=p[i].y;
            pozll=i;
        }
    }
    punct aux;
    aux.x=p[1].x;
    aux.y=p[1].y;
    p[1].x=p[pozll].x;
    p[1].y=p[pozll].y;
    p[pozll].x=aux.x;
    p[pozll].y=aux.y;
    sort(p+2,p+n+1,cmp);
    int top=2;
    infasuratoare[1]=1;
    infasuratoare[2]=2;
    i=3;
    while(i<=n)
    {
        if(ccw(p[infasuratoare[top-1]],p[infasuratoare[top]],p[i])>=0)
        {
            top++;
            infasuratoare[top]=i;
            i++;
        }
        else
        {
            top--;
        }
    }
    int j;
    double h,hmax=0,ldmax=0,lsmax=0,s,smin=INF,ld,ls;
    p[n+1].x=LL.x;
    p[n+1].y=LL.y;
    for(i=1;i<=top;i++)
        {
          hmax=ldmax=lsmax=0;
          for(j=1;j<=top;j++)
            if(j!=i&&j!=i+1)
            {
                h=inaltime(p[infasuratoare[j]],p[infasuratoare[i]],p[infasuratoare[i+1]]);
                if(h>hmax)
                    hmax=h;
                if(obtuz(p[infasuratoare[i]],p[infasuratoare[i+1]],p[infasuratoare[j]])==true)
                {
                    if(lungime(p[infasuratoare[i]],p[infasuratoare[j]])>lungime(p[infasuratoare[i+1]],p[infasuratoare[j]]))
                    {
                        ld=sqrt(lungime(p[infasuratoare[i+1]],p[infasuratoare[j]])*lungime(p[infasuratoare[i+1]],p[infasuratoare[j]])-h*h);
                        if(ld>ldmax)
                            ldmax=ld;
                    }
                    else
                    {
                        ls=sqrt(lungime(p[infasuratoare[i]],p[infasuratoare[j]])*lungime(p[infasuratoare[i]],p[infasuratoare[j]])-h*h);
                        if(ls>lsmax)
                            lsmax=ls;
                    }
                }
            }
            s=hmax*(lungime(p[infasuratoare[i]],p[infasuratoare[i+1]])+lsmax+ldmax);
            if(s<smin)
                smin=s;
        }
    printf("%.2lf",smin);

    return 0;
}