Cod sursa(job #176318)

Utilizator DorinOltean Dorin Dorin Data 11 aprilie 2008 00:11:48
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
# include <stdio.h>

//using namespace std;

# define input "regiuni.in"
# define output "regiuni.out"

# define maxm 1010
# define max 1001

# define mod 1009

int n,m,x,y,i,k,rez,val;
int s,s2,val2,ld, j;

long nr,poz;

struct dreapta
{
	int x,y,z;
}v[max];

struct lista
{
	int x,y;
	lista * urm;
}*g[max];

void adauga(int p,int x,int y)
{
     lista * f = new lista;
     f->x = x;
     f->y = y;
	 f->urm = g[p];
	 g[p] = f;
}
inline int semn(int x) { return x < 0 ? -1 : 1; } 

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);

	scanf("%d%d",&n,&m);

	for(i = 1;i<=n;++i)
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z);

    rez = 1;

	for(k = 1;k<=m;k++)
	{
		scanf("%d%d",&x,&y);
		adauga(rez,x,y);
    }
    for ( i = 1; i<=n; i++)
    {
        ld = rez;
        int nou = 0;
        for( j = 1; j<= rez; j++)
        {
             lista * f = g[j];
             lista * e = f;
             x = f->x;
             y = f->y;
             f=f->urm;
             val = v[i].x * x + v[i].y * y + v[i].z;
             s = semn(val);
             lista * r = new lista;
             r->x = x;
             r->y = y;
             g[j] = r;
             delete e;
             while(f)
             {
                 e = f;
                 
                 x = f->x;
                 y = f->y;

                 val2 = v[i].x * x + v[i].y * y + v[i].z;
                 s2 = semn(val2);
                 if(s2 == s)
                  adauga(j,x,y);
                 else
                 {
                     if(!nou)
                        adauga(++ld,x,y),nou = 1;
                     else
                        adauga(ld,x,y);
                 }
                 
                 f=f->urm;
                 delete e;
             }
        }
        rez = ld;
    }  

	printf("%d",rez);

	return 0;
}