Cod sursa(job #1104932)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 11 februarie 2014 11:24:28
Problema Stalpi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,viz[205],k;
double l[205],sol[3][205],solmax;
struct punct
{
    int x,y,d;
}v[205];
punct stv[205];
bool cmp(punct a,punct b)
{
    return a.x<b.x;
}
void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].d);
    }
}
int main()
{
    freopen("mosia.in","r",stdin);
    freopen("mosia.out","w",stdout);

    citire();
    sort(v+1,v+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        viz[i]=1;
        while(k>=2 && ((v[i].y-stv[k-1].y)*(stv[k].x-stv[k-1].x)-(stv[k].y-stv[k-1].y)*(v[i].x-stv[k-1].x))>0)
        {
            viz[k]=0;
            k--;
        }
        stv[++k]=v[i];
    }
    for(int i=n;i>=1;i--)
        if(viz[i]==0)
        {
            viz[i]=1;
            stv[++k]=v[i];
        }
    stv[0]=stv[k];
    stv[k+1]=stv[1];
    for(int i=1;i<=k;i++)
    {
        l[i]=sqrt((double)((stv[i-1].x-stv[i+1].x)*(stv[i-1].x-stv[i+1].x)+(stv[i-1].y-stv[i+1].y)*(stv[i-1].y-stv[i+1].y)));
    }
    sol[0][1]=0;
    sol[1][1]=stv[1].d*l[1]/2;
    for(int i=2;i<=k;i++)
    {
        if(sol[0][i-1]<sol[1][i-1])
            sol[0][i]=sol[1][i-1];
        else
            sol[0][i]=sol[0][i-1];
        sol[1][i]=sol[0][i-1]+stv[i].d*l[i]/2;
    }
    solmax=sol[1][k];;
    if(sol[0][k]>solmax)
        solmax=sol[0][k];
    printf("%.6lf",solmax);
    return 0;

}