Pagini recente » Cod sursa (job #82640) | Cod sursa (job #744672) | Cod sursa (job #1862095) | Cod sursa (job #712182) | Cod sursa (job #97724)
Cod sursa(job #97724)
#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;
}