Pagini recente » Cod sursa (job #1100832) | Cod sursa (job #654826) | Cod sursa (job #2387226) | Cod sursa (job #2830797) | Cod sursa (job #22898)
Cod sursa(job #22898)
#include<fstream.h>
long long B[50003],client[50003][2],i,n,sediu[2],cadr1[50003],cadr2[50003],st,dr,nr;
void merge_sort(long long l, long long r)
{
long 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 && (client[cadr1[i]][0]*client[cadr1[j]][1] < client[cadr1[j]][0]*client[cadr1[i]][1])))
B[k++] = cadr1[i++];
else
B[k++] = cadr1[j++];
for (k = l; k <= r; k++) cadr1[k] = B[k];
}
void merge_sort2(long long l,long long r)
{
long long m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort2(l, m);
merge_sort2(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && (client[cadr2[i]][0]*client[cadr2[j]][1] < client[cadr2[j]][0]*client[cadr2[i]][1])))
B[k++] = cadr2[i++];
else
B[k++] = cadr2[j++];
for (k = l; k <= r; k++) cadr2[k] = B[k];
}
int main()
{ifstream f("pachete.in");
f>>n;
f>>sediu[0]>>sediu[1];
for(i=1;i<=n;i++)
f>>client[i][0]>>client[i][1];
for(i=1;i<=n;i++)
{client[i][0]-=sediu[0];
client[i][1]-=sediu[1];
}
for(i=1;i<=n;i++)
{if(client[i][1]>0)
//este deasupra sediului
cadr1[++cadr1[0]]=i;
else
if(client[i][1]<0)
{cadr2[++cadr2[0]]=i;
client[i][1]=client[i][1]*(-1);
}
else
if(client[i][1]==0)
{if(client[i][0]<sediu[0]&&!st)
st++;
if(client[i][0]>sediu[0]&&!dr)
dr++;
}
}
if(cadr1[0]) merge_sort(1,cadr1[0]);
if(cadr2[0]) merge_sort2(1,cadr2[0]);
memset(B,0,sizeof(B));
for(i=1;i<=cadr1[0];i++)
{nr++;
while(client[cadr1[i]][0]*client[cadr1[i+1]][1]==client[cadr1[i+1]][0]*client[cadr1[i]][1])
i++;
}
for(i=1;i<=cadr2[0];i++)
{nr++;
while(client[cadr2[i]][0]*client[cadr2[i+1]][1]==client[cadr2[i+1]][0]*client[cadr2[i]][1])
i++;
}
nr=nr+st+dr;
ofstream g("pachete.out");
g<<nr;
g.close();
return 0;
}