Cod sursa(job #39334)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 26 martie 2007 17:26:59
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
# include <stdio.h>
# include <stdlib.h>

const int MAX=1000;

typedef struct PUNCT {long int x,y;};
PUNCT p[MAX+1];
typedef struct DREAPTA {long int a,b,c;};
DREAPTA m[MAX+1];
typedef struct NOD {PUNCT p; NOD *next;};
struct {NOD *prim, *ultim;} grup[MAX+1];
int nrg,n,mm;

void citire()
{
FILE *f=fopen("regiuni.in","r");
fscanf(f,"%d%d",&mm,&n);
int i;
for (i=1;i<=mm;i++)
	fscanf(f,"%ld%ld%ld",&m[i].a,&m[i].b,&m[i].c);
for (i=1;i<=n;i++)
	fscanf(f,"%ld%ld",&p[i].x,&p[i].y);
fclose(f);
}

void add(int i, PUNCT info)
{
NOD *q;
q=(NOD*) malloc (sizeof(NOD));
(*q).next=NULL;(*q).p=info;
if (grup[i].prim==NULL)
	grup[i].prim=grup[i].ultim=q;
else
	{
	(*grup[i].ultim).next=q;
	grup[i].ultim=q;
	}
}

void make_first_group()
{
int i;
for (i=1;i<=n;i++) add(1,p[i]);
nrg=1;
}

int signum(PUNCT p, DREAPTA d)
{
if (d.a*p.x+d.b*p.y+d.c>0) return 1;
return -1;
}

NOD* move(NOD *prv, NOD *q, int loc)
{
(*prv).next=(*q).next;
PUNCT save=(*q).p;
free(q);
add(loc,save);
return (*prv).next;
}


void split_groups()
{
int i,safe_nrg,j,ref;
NOD *q,*r,*prv;
for (i=1;i<=mm;i++)
	{
	safe_nrg=nrg;
	for (j=1;j<=safe_nrg;j++)
		{
		q=grup[j].prim;
		ref=signum((*q).p,m[i]);
		prv=q;q=(*q).next;
		while (q)
			if (signum((*q).p,m[i])!=ref)
				q=move(prv,q,nrg+1);
			else {prv=q;q=(*q).next;}
		if (grup[nrg+1].prim!=NULL) nrg++;
		}
	}
}

void scrie()
{
FILE *g=fopen("regiuni.out","w");
fprintf(g,"%d\n",nrg);
fcloseall();
}

void print_groups()
{
NOD *q;int i;
for (i=1;i<=nrg;i++)
	{
	printf("Grupul %d: ",i);
	q=grup[i].prim;
	while (q)
		{
		printf("%d %d ",(*q).p.x,(*q).p.y);
		q=(*q).next;
		}
	printf("\n");
	}
}

int main()
{
citire();
make_first_group();
split_groups();
scrie();
print_groups();
return 0;
}