Cod sursa(job #1117969)

Utilizator niktudyNica Tudor niktudy Data 23 februarie 2014 21:38:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.46 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin ("mosia.in");
ofstream fout ("mosia.out");
struct par
{
    int x,y,d,val;
} a[1010],aux,st,dr;
int n,ok[1010],c1,c2,c3;
double sol[1010],solmax;
int comp (par p1,par p2)
{
    if (!c1)
    {
        if (p1.y<=a[1].y&&p2.y>a[1].y)
            return 1;
        if (p1.y>a[1].y&&p2.y<=a[1].y)
            return 0;
        if (p1.y<=a[1].y&&p2.y<=a[1].y)
        {
            if (p1.x!=p2.x)
                return p1.x<p2.x;
            else
                return p1.y<p2.y;
        }
        if (p1.x!=p2.x)
            return p1.x>p2.x;
        if (p1.x==a[1].x)
            return p1.y>p2.y;
    }
    if (c1>0)
    {
        if (c1*p1.x+c2*p1.y+c3>=0&&c1*p2.x+c2*p2.y+c3<0)
            return 1;
        if (c1*p1.x+c2*p1.y+c3<0&&c1*p2.x+c2*p2.y+c3>=0)
            return 0;
        if (c1*p1.x+c2*p1.y+c3<0&&c1*p2.x+c2*p2.y+c3<0)
        {
            if (p1.x!=p2.x)
                return p1.x>p2.x;
            return p1.y>p2.y;
        }
        if (p1.x!=p2.x)
            return p1.x<p2.x;
        return p1.y<p2.y;
    }
    if (c1*p1.x+c2*p1.y+c3<=0&&c1*p2.x+c2*p2.y+c3>0)
        return 1;
    if (c1*p1.x+c2*p1.y+c3>0&&c1*p2.x+c2*p2.y+c3<=0)
        return 0;
    if (c1*p1.x+c2*p1.y+c3>0&&c1*p2.x+c2*p2.y+c3>0)
    {
        if (p1.x!=p2.x)
            return p1.x>p2.x;
        return p1.y>p2.y;
    }
    if (p1.x!=p2.x)
        return p1.x<p2.x;
    return p1.y<p2.y;
}
double calc (par p1,par p2,par p3)
{
    double baza=sqrt((double)((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y)));
    return baza*(p2.d)/2;
}
int main()
{
    int i;
    double rez;
    fin>>n;
    dr.x=-2000000000;
    dr.y=-2000000000;
    for (i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].d;
        a[i].val=i;
        if (a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))
        {
            aux=a[i];
            a[i]=a[1];
            a[1]=aux;
        }
        if (dr.x<a[i].x||(dr.x==a[i].x&&dr.y<a[i].y))
            dr=a[i];
    }
    fin.close ();
    st=a[1];
    c1=dr.y-st.y;
    c2=st.x-dr.x;
    c3=dr.x*st.y-dr.y*st.x;
    if (c1<0)
    {
        c1*=-1;
        c2*=-1;
        c3*=-1;
    }
    sort (a+2,a+n+1,comp);
    a[0]=a[n];
    a[n+1]=a[1];
    sol[1]=calc (a[0],a[1],a[2]);
    ok[1]=1;
    for (i=2;i<=n;i++)
    {
        rez=calc(a[i-1],a[i],a[i+1]);
        if (sol[i-1]>=sol[i-2]+rez)
        {
            sol[i]=sol[i-1];
            ok[i]=ok[i-1];
        }
        else
        {
            sol[i]=sol[i-2]+rez;
            ok[i]=ok[i-2];
        }
    }
    if (ok[n])
        solmax=sol[n-1];
    else
    {
        fout<<fixed<<setprecision(4)<<sol[n]<<'\n';
        fout.close ();
        return 0;
    }
    for (i=0;i<=n;i++)
    {
        a[i]=a[i+1];
        ok[i]=0;
    }
    a[n+1]=a[1];
    sol[1]=calc (a[0],a[1],a[2]);
    ok[1]=1;
    for (i=2;i<=n;i++)
    {
        rez=calc(a[i-1],a[i],a[i+1]);
        if (sol[i-1]>=sol[i-2]+rez)
        {
            sol[i]=sol[i-1];
            ok[i]=ok[i-1];
        }
        else
        {
            sol[i]=sol[i-2]+rez;
            ok[i]=ok[i-2];
        }
    }
    if (ok[n])
        sol[n]=sol[n-1];
    if (sol[n]>solmax)
        fout<<fixed<<setprecision(4)<<sol[n]<<'\n';
    else
        fout<<fixed<<setprecision(4)<<solmax<<'\n';
    fout.close ();
    return 0;
}