Cod sursa(job #37650)

Utilizator devilkindSavin Tiberiu devilkind Data 25 martie 2007 11:38:30
Problema Regiuni Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.24 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 1024

FILE *f = fopen("regiuni.in","rt"), *g = fopen("regiuni.out","wt");

long int pct[NMAX][2],dr[NMAX][3],n,m,i,j,k,sol,ord[NMAX],maxx,x;
long int a[NMAX][NMAX];

void citire()
{
fscanf(f,"%ld %ld",&n,&m);
for (i=1;i<=n;i++)
    fscanf(f,"%ld %ld %ld",&dr[i][0],&dr[i][1],&dr[i][2]);
for (i=1;i<=m;i++)
    fscanf(f,"%ld %ld",&pct[i][0],&pct[i][1]);
}

int comp(long int x, long int y)
{
long int i,ok=1,k1,k2;
for (i=1;i<=maxx;i++)
    if (a[x][i]!=a[y][i]) {ok=0;break;}
if (ok) return 0;
if (a[x][i]>a[y][i]) return 1;
return -1;
}

int cmp(const void *X, const void *Y)
{
long int x=* (long int *) X, y=* (long int *) Y,i;
i=comp(x,y);
return i;
}

void solve()
{
k=1;maxx=1;
for (i=1;i<=n;i++)
    {
    for (j=1;j<=m;j++)
        {
        x=dr[i][0]*pct[j][0]+dr[i][1]*pct[j][1]+dr[i][2];
        if (x<0) x=0;
           else x=1;
        a[j][k]= a[j][k]*2 + x;
        }
    if (i%20==0) {k++;maxx=k;}
    }
for (i=1;i<=m;i++)
    ord[i]=i;
qsort(ord,m+1,sizeof(long int),cmp);
sol=0;
for (i=1;i<=m;i++)
    if (comp(ord[i],ord[i+1])!=0) sol++;
fprintf(g,"%ld",sol);
}

int main()
{
citire();
solve();
fclose(f);
fclose(g);
return 0;
}