Cod sursa(job #554489)

Utilizator paul992Cirstean Paul paul992 Data 14 martie 2011 21:29:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#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;}