Cod sursa(job #164117)

Utilizator znakeuJurba Andrei znakeu Data 23 martie 2008 15:52:58
Problema Wanted Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 205

// incomplet?....

struct oras
{
	int x,y;	
};

oras v[MAXN];
int vizit[MAXN],rez=0,n;

int cmp(const void *a, const void *b)
{
	oras x=*(oras*)a, y=*(oras*)b;
	return x.x-y.x;
}

int wtfff(int s, int e, int d,int p)
{
	vizit[p]=1;
	if (d>rez)
		rez=d;
	int m=(s+e)/2;
	if (!vizit[m])
	{
		d+=v[p].y+abs(v[p].x-v[m].x)+v[m].y;
		//gigel e aici!
		if (d>rez)
			rez=d;
		//gigel e la stanga
		wtfff(s,m,d,m);
		//gigel e la dreapta
		if (m+1<e)
			wtfff(m+1,e,d,m);
	}
	vizit[p]=0;
}

int main()
{
	freopen("wanted.in","r",stdin);
	freopen("wanted.out","w",stdout);
	
	int i,j,P,X=-1;	
	
	scanf("%d",&n);

	for (i=0; i<n; i++)
		scanf("%d%d",&v[i].x,&v[i].y);

	qsort(v,n,sizeof(v[0]),cmp);
	for (i=0; i<n; i++)
		if (abs(v[i].x)+v[i].y<X || X==-1)
		{
			X=abs(v[i].x)+v[i].y;
			P=i;
		}
	
	wtfff(0,P,X,P);
	wtfff(P,n-1,X,P);
	
	
	printf("%d\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}