Cod sursa(job #75302)

Utilizator sealTudose Vlad seal Data 1 august 2007 03:07:11
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#include<string.h>
#define Nm 1000
int A[Nm],B[Nm],C[Nm],X[Nm],Y[Nm],n,m,r;

void read()
{
    int i;

    freopen("regiuni.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
        scanf("%d%d%d",A+i,B+i,C+i);
    for(i=0;i<m;++i)
        scanf("%d%d",X+i,Y+i);
}

void solve()
{
    int Reg[Nm],NewReg[Nm],Poz[Nm],Neg[Nm],i,j;

    r=1;
    memset(Reg,0,sizeof(Reg));
    for(i=0;i<n;++i)
    {
        memset(Poz,0,sizeof(Poz));
        memset(Neg,0,sizeof(Neg));
        memset(NewReg,0,sizeof(NewReg));
        for(j=0;j<m;++j)
            if(A[i]*X[j]+B[i]*Y[j]+C[i]>0)
                Poz[Reg[j]]=1;
            else
                Neg[Reg[j]]=1;
        for(j=0;j<r;++j)
            if(Poz[j] && Neg[j])
                NewReg[j]=r++;
        for(j=0;j<m;++j)
            if(NewReg[Reg[j]] && A[i]*X[j]+B[i]*Y[j]+C[i]>0)
                Reg[j]=NewReg[Reg[j]];
    }
}

void write()
{
    freopen("regiuni.out","w",stdout);
    printf("%d\n",r);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}