Cod sursa(job #128927)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 28 ianuarie 2008 11:40:36
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
/*
Sursa de palianos [za_wolf that is]
as in, acum compileaza
algo.h este numele backward compatible pentru algorithm
labs?, abs este implementat in algorithm ca template, deci nu te intereseaza ce tip ii dai in principiu
*/

#include<stdio.h>
#include<math.h>
#include<algo.h>
#define NMAX 130000
using namespace std;
struct kkt
{
	long X,Y,Z;
};
struct kkkt
{
	long in,sf;
};

struct kkkkt
{
	long punct,curent;
};
kkkkt queue[NMAX];
kkt inc[NMAX],pct[NMAX],aux;
kkkt veciny[NMAX],vecinx[NMAX];
long i,j,a,k,l,m,s,rez[NMAX],n,curent,q,x[NMAX],in,sf;
int cmpf_1(const kkt a,const kkt b)
{
	return(a.X<b.X?a.X<b.X:((a.X==b.X)?(a.Y<b.Y):(a.X<b.X)));
}

int cmpf_2(const kkt a,const kkt b)
{
	return(a.Y<b.Y?a.Y<b.Y:((a.Y==b.Y)?(a.X<b.X):(a.Y<b.Y)));
}

int main()
{
	freopen("primar.in","r",stdin);
	freopen("primar.out","w",stdout);
/*	scanf("%ld",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%ld%ld",&pct[i].X,&pct[i].Y);
		pct[i].Z=i;
		inc[i]=pct[i];
	}*/
	scanf("%ld%ld",&i,&j);
	printf("%ld\n",i+j);
/*	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
		if (pct[i].Y>pct[i+1].Y) {aux=pct[i]; pct[i]=pct[i+1]; pct[i+1]=aux; a=1;}
	}

	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
		if (pct[i].X>pct[i+1].X) {aux=pct[i]; pct[i]=pct[i+1]; pct[i+1]=aux; a=1;}
	}
*/

	sort(pct+1,pct+n+1,cmpf_1);
	pct[0].X=2000000001;
	pct[0].Y=2000000001;
	pct[n+1].X=2000000001;
	pct[n+1].Y=2000000001;
	for (i=1;i<=n;i++)
	{
		if (pct[i].X==pct[i+1].X)
			vecinx[pct[i].Z].sf=pct[i+1].Z;

		if (pct[i].X==pct[i-1].X)
			vecinx[pct[i].Z].in=pct[i-1].Z;
	}

/*	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
		if (pct[i].Y>pct[i+1].Y) {aux=pct[i]; pct[i]=pct[i+1]; pct[i+1]=aux; a=1;}
	} */

	sort(pct+1,pct+n+1,cmpf_2);
	for (i=1;i<=n;i++)
	{
		if (pct[i].Y==pct[i+1].Y)
			veciny[pct[i].Z].sf=pct[i+1].Z;

		if (pct[i].Y==pct[i-1].Y)
			veciny[pct[i].Z].in=pct[i-1].Z;
	}
	a=1;
	s=0;
	while (a)
	{
		a=0;
		for (i=1;i<=n;i++)
		if (x[i]==0)
		{
			a=1;
			in=1;
			sf=1;
			queue[1].punct=i;
			queue[1].curent=1;
			s+=1;
			while (in<=sf)
			{
				if (x[vecinx[queue[in].punct].in]==0)
				{
					x[vecinx[queue[in].punct].in]=1;
					queue[++sf].punct=vecinx[queue[in].punct].in;
					if (queue[in].curent==1) queue[sf].curent=-1;
					else
					queue[sf].curent=1;
					rez[vecinx[queue[in].punct].in]=queue[sf].curent;
					s+=queue[sf].curent;
				}

				if (x[vecinx[queue[in].punct].sf]==0)
				{
					x[vecinx[queue[in].punct].sf]=1;
					queue[++sf].punct=vecinx[queue[in].punct].sf;
					if (queue[in].curent==1) queue[sf].curent=-1;
					else
					queue[sf].curent=1;
					rez[vecinx[queue[in].punct].sf]=queue[sf].curent;
					s+=queue[sf].curent;
				}


				if (x[veciny[queue[in].punct].in]==0)
				{
					x[veciny[queue[in].punct].in]=1;
					queue[++sf].punct=veciny[queue[in].punct].in;
					if (queue[in].curent==1) queue[sf].curent=-1;
					else
					queue[sf].curent=1;
					rez[veciny[queue[in].punct].in]=queue[sf].curent;
					s+=queue[sf].curent;
				}

								if (x[veciny[queue[in].punct].sf]==0)
				{
					x[veciny[queue[in].punct].sf]=1;
					queue[++sf].punct=veciny[queue[in].punct].sf;
					if (queue[in].curent==1) queue[sf].curent=-1;
					else
					queue[sf].curent=1;
					rez[veciny[queue[in].punct].sf]=queue[sf].curent;
					s+=queue[sf].curent;
				}
				in++;
			}
		}
	}
	s=abs(s);
/*	printf("%ld\n",s);
	for (i=1;i<=n;i++)
	{
		if (rez[i]==-1) rez[i]=0;
		printf("%ld ",rez[i]);
	}
	printf("\n");
  */
	return 0;
}