Cod sursa(job #97724)

Utilizator vrajalaMihai Viteazu, razboinicu luminii vrajala Data 8 noiembrie 2007 11:45:34
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2505
#define Cmax 128


int N;
int a[Nmax][2*Nmax];

int x1[Nmax],x2[Nmax],y1[Nmax],y2[Nmax];
int y[2*Nmax],what[Nmax];
int c[Nmax];

inline int swap(int &a,int &b) { int aux=a;a=b;b=aux; }

void citire()
{
 int i;
 freopen("teren.in","r",stdin);
 scanf("%d",&N);
 for (i=1;i<=N;++i)
	{
	 scanf("%d %d %d %d %d",&x1[i],&y1[i],&x2[i],&y2[i],&c[i]);
	 if (x1[i]>x2[i]) swap(x1[i],x2[i]);
	 if (y1[i]<=y2[i]) what[2*i]=1;
	 else   {
			 what[2*i-1]=1;
			 swap(y1[i],y2[i]);
			}
	 y[2*i-1]=y1[i];
	 y[2*i]=y2[i];
	}
 fclose(stdin);
}

void qsort(int st,int dr)
{
	int i=st,j=dr,m=y[(st+dr)>>1];
	while (i<=j)
		{
			while (y[i]<m) ++i;
			while (y[j]>m) --j;
			if (i<=j)
				{
					swap(y[i],y[j]);
					swap(what[i],what[j]);
					++i;
					--j;
				}
		}
  if (i<dr) qsort(i,dr);
  if (st<j) qsort(st,j);
}

qsort_dr(int st,int dr)
{
	int i=st,j=dr,mx=x1[(st+dr)>>1],my=y1[(st+dr)>>1];
	while (i<=j)
		{
			while ((x1[i]<mx)||((x1[i]==mx)&&(y1[i]<my))) ++i;
			while ((x1[j]>mx)||((x1[j]==mx)&&(y1[j]>my))) --j;
			if (i<=j)
				{
					swap(x1[i],x1[j]);
					swap(x2[i],x2[j]);
					swap(y1[i],y1[j]);
					swap[y2[i],y2[j]);
					++i;
					--j;
				}
		}
  if (i<dr) qsort_dr(i,dr);
  if (st<j) qsort_dr(st,j);
}

void memorizare()
{
 int i,j,k;
 for (i=N;i>0;--i)
	{
	 k=i+1;
	 while (x1[k]<x2[i]) ++k;
	 if (x1[k]>x2[i]) continue;
	 for (j=1;j<=2*N;++j)
		if ( (y[j]!=y[j-1])&&(y1[i]<=y[j]) )
			//
			{
			 while ( (x1[k]==x2[i])&&(y1[k]>y[j]) ) ++k;
			 if (x1[k]==x2[i]) a[i][j]=a[k][j]+x2[i]-x1[i];
				else a[i][j]=x2[i]-x1[i];
			}

	}
		
}

void solve()
{
 int i,j;
 
}

int main()
{
	citire();
	qsort(1,2*N);
	qsort_dr(1,N);
	x1[N+1]=2000000000;
	memorizare();
	return 0;
}