Cod sursa(job #45024)

Utilizator c_sebiSebastian Crisan c_sebi Data 31 martie 2007 22:21:07
Problema Regiuni Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#define MAX 1001

struct Punct {int x, y, gr;} p[MAX];
struct Dreapta {int a, b, c;} dr[MAX];

int np, ndr, nrg, reg;

void intercl (Punct a[], int s, int d, int m)
{
	int  i, j, k;
	Punct x[MAX+1], y[MAX+1];
	for (i=s; i<=m; i++) x[i]=a[i];
	for (i=m+1; i<=d; i++) y[i]=a[i];
	x[m+1].gr=30000; y[d+1].gr=30000;
	i=s; j=m+1;
	for (k=s; k<=d; k++)
		if (x[i].gr<y[j].gr) {a[k]=x[i]; i++; }
		else { a[k]=y[j]; j++;}
}


void sort (Punct a[], int s, int d)
{
	if (s==d) return;
	else
		{
			int m=(s+d)/2;
			sort (a, s, m);
			sort (a, m+1, d);
			intercl (a, s, d, m);
		}
}

/*void quick (Punct x[], int st, int dr)
{
	int i, ii, j, jj, aux2;
	Punct aux;
	i=st; j=dr;
	ii=0; jj=-1;
 if (st<dr)
{	while (i<j)
		{
			if (x[i].gr>x[j].gr)
				{ aux=x[i]; x[i]=x[j]; x[j]=aux;
				  aux2=-ii; ii=-jj; jj=aux2;
				}
			i=i+ii;
			j=j+jj;
		}
	quick(x, st, i-1);
	quick(x, i+1, dr);
 }
}*/

int main()
{
	FILE *f, *g;
	f=fopen ("regiuni.in", "r");
	g=fopen ("regiuni.out", "w");
	int a, b, c, i, j, ok, val;
	fscanf (f, "%d %d", &ndr, &np);
	for (i=1; i<=ndr; i++)
		fscanf (f, "%d %d %d", &dr[i].a, &dr[i].b, &dr[i].c);
	for (i=1; i<=np; i++)
		{fscanf (f, "%d %d", &p[i].x, &p[i].y);
		p[i].gr=1;
		}
	fclose(f);
	nrg=2;
	for (i=1; i<=ndr; i++)
		{
			a=dr[i].a; b=dr[i].b; c=dr[i].c;
			for (j=1; j<=np; j++)
			  {ok=0;
			  val=p[j].gr;
			  while (j<=np && p[j].gr==val)
				  {if (a*p[j].x + b*p[j].y + c < 0)
							p[j].gr=nrg, ok=1;
					j++;
				  }
           if (p[j].gr!=val) j--;
			  if (ok) nrg++;
			  }
		  sort (p, 1, np);
		}
	for (i=1; i<=np; i++)
		{
			val=p[i].gr;
			while (p[i].gr==val && i<=np) i++;
			if (p[i].gr!=val) i--;
			reg++;
		}
	fprintf (g, "%d\n", reg);
	fclose(g);
	return 0;
}