Nu aveti permisiuni pentru a descarca fisierul grader_test15.ok
Cod sursa(job #38310)
Utilizator | Data | 25 martie 2007 17:15:51 | |
---|---|---|---|
Problema | Regiuni | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.87 kb |
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define nmax 1024
#define mmax 1024
int n,m,a[mmax],b[mmax],c[mmax],i,j,x,y,ord[nmax],sol;
char s[nmax][mmax/8];
int fc(const void *x,const void *y)
{
i=0;
while ((s[*(int*)x][i]==s[*(int*)y][i])&&(i<(m/8+1)))
++i;
return (s[*(int*)x][i]-s[*(int*)y][i]);
}
int main()
{
freopen("regiuni.in","r",stdin);
freopen("regiuni.out","w",stdout);
scanf("%d%d",&m,&n);
for (i=0;i<m;i++)
scanf("%d%d%d",a+i,b+i,c+i);
for (j=0;j<n;j++)
{
ord[j]=j;
scanf("%d%d",&x,&y);
for (i=0;i<m;i++)
if ((a[i]*x+b[i]*y+c[i])>0)
s[j][i/8]|=(1<<(i%8));
}
qsort((void*)ord,n,sizeof(ord[0]),fc);
sol=1;
for (j=1;j<n;j++)
if (fc(&ord[j-1],&ord[j]))
++sol;
printf("%d\n",sol);
return 0;
}