Cod sursa(job #86411)

Utilizator coderninuHasna Robert coderninu Data 24 septembrie 2007 17:37:34
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 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;
    };


struct nod
    {
     int inf;
     struct nod * urm;
    };
typedef nod * list;


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


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


int poz(punct,dreapta);
void init();


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()
{
 init();
 int temp, loc, add;
 list p, last;
 for (i=1; i<=n; i++)
     {
      temp=0;
      for (j=1; j<=gmax; j++)
	  {
	   add=0;
	   loc=poz(pct[v[j]->inf],dr[i]);
	   for (p=v[j]->urm, last=v[j]; p; p=p->urm)
	       if (poz(pct[p->inf],dr[i])!=loc)
		   {
		    last->urm=last->urm->urm;
		    if (add)
			{
			 p->urm=v[gmax+temp];
			 v[gmax+temp]=p;
			 p=last;
			}
		    else
			{
			 temp++;
			 add=1;
			 p->urm=v[gmax+temp];
			 v[gmax+temp]=p;
			 p=last;
			}
		   }
	       else last=last->urm;
	  }
      gmax+=temp;
     }
}


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

void init()
{
 v[1]=new nod;
 v[1]->inf=1;
 v[1]->urm=NULL;
 list last=v[1];
 for (i=2; i<=m; i++)
     {
      list p=new nod;
      p->inf=i;
      p->urm=NULL;
      last->urm=p;
      last=p;
     }
}