Pagini recente » Cod sursa (job #991781) | Cod sursa (job #2607151) | Cod sursa (job #97615) | Cod sursa (job #2884346) | Cod sursa (job #7292)
Cod sursa(job #7292)
#include<fstream.h>
int long elimin[50003],key[50003],keyy[50003],key1[50003],i,j,c[50003][2],sursa[2],n,sus[50003],jos[50003],nr,B[50003];
void merge_sort(int long l, int long r)
{
int long m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort(l, m);
merge_sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && sus[i] < sus[j]))
{keyy[k]=key[i];
B[k++] =sus[i++];}
else
{keyy[k]=key[j];
B[k++] = sus[j++];}
for (k = l; k <= r; k++) {key[k]=keyy[k]; sus[k] = B[k];}
}
void gaseste_drum(int long i)
{elimin[key[i]]=1;
if(c[key[i]][0]>0)
{
for(j=i+1;j<=n;j++)
if(c[key[j]][0]>0&&c[key[j]][0]<=c[key[i]][0])
gaseste_drum(j);
if(j==n+1)
return;
}
else{
for(j=i+1;j<=n;j++)
if(c[key[j]][0]<=0&&c[key[j]][0]>=c[key[i]][0])
gaseste_drum(j);
if(j==n+1)
return;
}
}
int main()
{ifstream f("pachete.in");
f>>n;
f>>sursa[0]>>sursa[1];
for(i=1;i<=n;i++)
{f>>c[i][0]>>c[i][1];
c[i][0]-=sursa[0];
c[i][1]-=sursa[1];
if(c[i][1]>=0)
{sus[++sus[0]]=c[i][1];
key[sus[0]]=i;
//key[sus[0]]=i;
}
else
{c[i][1]*=(-1);
jos[++jos[0]]=c[i][1];
key1[jos[0]]=i;
}
}
n=sus[0];
key[0]=n;
merge_sort(1,sus[0]);
memcpy(sus,key,sizeof(key));
for(i=1;i<=sus[0];i++)
key[sus[0]-i+1]=sus[i];
for(i=1;i<=sus[0];i++)
{
if(!elimin[key[i]])
{nr++;
gaseste_drum(i);
}
}
n=jos[0];
merge_sort(1,n);
memcpy(key,key1,sizeof(key1));
key[0]=n;
memcpy(sus,jos,sizeof(sus));
merge_sort(1,n);
memcpy(sus,key,sizeof(key));
for(i=1;i<=sus[0];i++)
key[sus[0]-i+1]=sus[i];
for(i=1;i<=sus[0];i++)
{
if(!elimin[key[i]])
{nr++;
gaseste_drum(i);
}
}
ofstream g("pachete.out");
g<<nr;
g.close();
return 0;
}