Cod sursa(job #85270)

Utilizator coderninuHasna Robert coderninu Data 20 septembrie 2007 18:43:28
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define infile "regiuni.in"
#define outfile "regiuni.out"
#define nmax 1001

struct dreapta
    {
     int a,b,c;
    };
struct punct
    {
     int x, y;
    };

int n, m, i, j, k, rez, gmax;
dreapta dr[nmax];
punct pct[nmax];
short v[nmax][nmax];

void readdata();
void writedata();
void solve();

int poz(punct,dreapta);

int main()
{
 readdata();
 solve();
 writedata();
 return 0;
}

void readdata()
{
 freopen(infile, "r", stdin);
 scanf("%d %d\n", &n, &m);
 for (i=1; i<=n; i++)
     scanf("%d %d %d\n", &dr[i].a, &dr[i].b, &dr[i].c);
 for (i=1; i<=m; i++)
     scanf("%d %d\n", &pct[i].x, &pct[i].y);
 fclose(stdin);
}

void writedata()
{
 freopen(outfile, "w", stdout);
 printf("%d\n", gmax);
 fclose(stdout);
}

void solve()
{
 int loc, modif, temp;
 v[1][0]=m;
 for (i=1; i<=m; i++) v[1][i]=1;
 gmax=temp=1;
 for (i=1; i<=n; i++)
     {
     for (j=1; j<=gmax; j++)
	 if (v[j][0]>1)
	     {
	      for (k=1; k<=m && !v[j][k]; k++);
	      loc=poz(pct[k],dr[i]);
	      modif=0;
	      for (k++; k<=m; k++)
		  if (v[j][k] && loc!=poz(pct[k],dr[i]))
		      {
		       if (!modif)
			   {
			    modif=1;
			    temp++;
			   }
		       v[j][k]=0;
		       v[j][0]--;
		       v[temp][0]++;
		       v[temp][k]=1;
		      }
	     }
     gmax=temp;
     }
}

int poz(punct p, dreapta d)
{
 return d.a*p.x+d.b*p.y+d.c<0;
}