Cod sursa(job #37769)

Utilizator butyGeorge Butnaru buty Data 25 martie 2007 12:28:12
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.93 kb
#include<stdio.h>
typedef int db;
int N,M;
int B[1024][4],C[1024][1024],P[1024],anou[1024],NR_anou,unde[1024],Arbore[1024];
struct punct
{
	db x,y;
};
punct A[1024];
int semn(db aa,db bb,db cc,punct C)
{
    if(aa*C.x+bb*C.y+cc<0)
        return 2;
    return 1;
}  
void cit()
{
    freopen("regiuni.in","r",stdin);
    int i;
   	scanf("%d%d",&M,&N);
	for(i=1;i<=M;i++)
		scanf("%d%d%d",&B[i][0],&B[i][1],&B[i][2]);
   	for(i=1;i<=N;i++)
		scanf("%d%d",&A[i].x,&A[i].y);
}
int arb(int i)
{
    if(P[P[i]])
        return arb(P[i]);
    return i;
}
void adauga(int i,int k)
{
    C[k][++C[k][0]]=i;
    unde[i]=C[k][0];
    if(C[k][0]>1)
        P[i]=C[k][C[k][0]/2];
    else
        P[i]=0;
}
int arb_nou(int k)
{
    if(anou[k]==0)
       anou[k]=++NR_anou;
    return anou[k];
}
void elim(int i,int k)
{
    int l=P[i];
    C[k][unde[i]]=C[k][C[k][0]--];
    P[C[k][unde[i]]]=l;
}
void rez()
{
    int i,sign,j,a=0,e,val,s;
//    NR_anou=1;
    for(i=1;i<=N;i++)
    {

        sign=semn(B[1][0],B[1][1],B[1][2],A[i]);
        adauga(i,sign);
        P[arb(i)]=-sign;
        if(a!=sign)
            Arbore[arb(i)]=++NR_anou;
        a=sign;
    }
    for(i=2;i<=M;i++)
    {
        for(j=1;j<=N;j++)
        {
            anou[j]=0;
            if(P[j]<0)
                P[j]=0;
        }
        for(j=1;j<=N;j++)
        {
            a=arb(j);
            sign=semn(B[i][0],B[i][1],B[i][2],A[j]);
            if( P[a] == 0)
                P[a]=-sign;
            else
                if(P[a]!=-sign)
                {
                    s=arb_nou(a);
                    elim(j,Arbore[a]);
                    adauga(j,s);
                    Arbore[j]=s;
                }
        }
    }
    
}
void scr()
{
    freopen("regiuni.out","w",stdout);
    printf("%d\n",NR_anou);
	fclose(stdout);
}
int main()
{
    cit();
    rez();
    scr();
	return 0;
}