Pagini recente » Cod sursa (job #551440) | Statistici Militaru Adrian (DonPushme) | Monitorul de evaluare | Rating Timofte Andrei (Andrei12.3) | Cod sursa (job #554489)
Cod sursa(job #554489)
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct punct
{int x,y,d;};
punct p[1001];
int n,ord[1001],k,viz[1001];
double v[1001],best[1001],maxx;
bool cmp(punct l,punct r)
{return l.x<r.x;}
double dist(punct p1,punct p2)
{return sqrt((double)((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y)));}
void read()
{
scanf("%d ",&n);
for(int i=1;i<=n;i++)
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].d);
}
void dinamic(int l,int r)
{
best[l-2]=0;
best[l-1]=v[l-1];
for(int i=l;i<=r;i++)
{
best[i]=max(best[i-1],best[i-2]+v[i]);
maxx=max(best[i],maxx);
}
}
void solve()
{int x=1;
ord[++k]=1;
viz[1]=1;
sort(&p[1],&p[n+1],cmp);
for(int i=1;i<n;i++)
if(p[i].x==p[i+1].x&&p[i].y>p[i+1].y)swap(p[i],p[i+1]);
for(int i=2;i<=n;i++)
if(p[i].y<=p[x].y&&!viz[i])
{ord[++k]=i;viz[i]=1;}
x=ord[k];
for(int i=n;i>1;i--)
if(p[i].y>=p[x].y&&!viz[i])
{ord[++k]=i;viz[i]=1;}
ord[0]=ord[n];
ord[n+1]=ord[1];
for(int i=1;i<=n;i++)
v[i]=(double)(dist(p[ord[i-1]],p[ord[i+1]])*p[ord[i]].d)/2;
//for(int i=1;i<=n;i++)
//printf("%lf ",v[i]);
dinamic(2,n-1);
dinamic(3,n);
}
void print()
{
printf("%.4lf ",maxx);
}
int main()
{freopen("mosia.in","r",stdin);
freopen("mosia.out","w",stdout);
read();
solve();
print();
return 0;}