Cod sursa(job #40255)

Utilizator devilkindSavin Tiberiu devilkind Data 27 martie 2007 12:20:17
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#define NMAX 1010

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

long int pct[NMAX][2],dr[NMAX][3],i,j,k,gr[NMAX],nr,n,m,st,drt,pct2[NMAX*2][2],mid,st1,cnt,nrc;
long int h[2*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]);
}

void solve()
{
gr[m+1]=1000000000;
for (i=1;i<=m;i++)
    gr[i]=1;
for (i=1;i<=n;i++)
    {
    st=1;
    drt=st+1;
    nrc=1;
    while (drt<=m)
    {
    while (gr[drt]==gr[drt-1])
          drt++;
    drt--;
    mid=m+1;
    st1=1;
    for (j=st;j<=drt;j++)
        if (dr[i][0]*pct[j][0]+dr[i][1]*pct[j][1]+dr[i][2]<0) {pct2[st1][0]=pct[j][0]; 
                                                              pct2[st1][1]=pct[j][1];
                                                              st1++;}
                                                              else 
                                                              {pct2[mid][0]=pct[j][0]; 
                                                              pct2[mid][1]=pct[j][1];
                                                              mid++;}
    cnt=st;
    for (j=1;j<=st1-1;j++ , cnt++)
        {
        pct[cnt][0]=pct2[j][0];
       	pct[cnt][1]=pct2[j][1];
	    gr[cnt]=nrc;
	    }
    nrc++;
    for (j=m+1;j<=mid-1;j++ , cnt++)
	{
	pct[cnt][0]=pct2[j][0];
	pct[cnt][1]=pct2[j][1];
    gr[cnt]=nrc;
    }    
    nrc++;
    st=drt+1;
    drt=st+1;
    }
    }
nrc=0;
for (i=1;i<=m;i++)
	if (!(h[gr[i]])) {h[gr[i]]=1;
			nrc++;}
fprintf(g,"%ld",nrc);
}

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