Cod sursa(job #47133)

Utilizator ionel71089lescai ionel ionel71089 Data 3 aprilie 2007 12:55:31
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<fstream.h>
//ifstream f("regiuni.in");
ofstream g("regiuni.out");
typedef struct _punct
	{
	int x,y;
	}Punct;
//typedef struct _dreapta
//	{
//	int a,b,c;
//	}Dreapta;
typedef struct _lista
	{
	Punct pct;
	_lista *st,*dr;
	}*Lista;
typedef struct _grup
	{
	Lista p,u;
	}Grup;

typedef struct _listagrup
	{
	Grup G;
	_listagrup *urm;
	}*LG;


int n,m,nrg=1;
long Z;
LG pg,ug;

void adauga (LG &p,LG &u)
	{
	LG nou=new _listagrup;
	nou->urm=0;
	nou->G.p=nou->G.u=0;
	if(p==0)p=u=nou;
	else
		u->urm=nou,u=nou;
	}



//Dreapta *d;
void adauga(LG &X,int x,int y)
	{
	Lista nou=new _lista;
	nou->pct.x=x,nou->pct.y=y;nou->st=nou->dr=NULL;
	if(X->G.p==NULL)
		X->G.p=X->G.u=nou;
	else
		nou->st=X->G.u,X->G.u->dr=nou,X->G.u=nou;
	}
void sterge(Lista &del,LG X)
	{
	if(del==X->G.p)
		{
		X->G.p=X->G.p->dr;
		X->G.p->st=NULL;
		delete del;
		return;
		}
	if(del==X->G.u)
		{
		X->G.u=X->G.u->st;
		X->G.u->dr=NULL;
		delete del;
		return;
		}
	del->st->dr=del->dr;
	del->dr->st=del->st;
	delete del;
	}
void afisare()
	{
	LG i;
	Lista j;
	for(i=pg;i;i=i->urm,g<<"\n")
		{
		g<<i<<":";
		for(j=i->G.p;j;j=j->dr)
			g<<"("<<j->pct.x<<" "<<j->pct.y<<")";
		}
	}
int main()
{
adauga(pg,ug);
ifstream f("regiuni.in");
int i,j,x,y,nrgn,gasit,a,b,c;
f>>n>>m;
//d=new Dreapta[m+1];
for(i=1;i<=n;i++)
	f>>a>>b>>c;
LG grup=pg;
for(i=1;i<=m;i++,grup=grup->urm)
	f>>x>>y,adauga(grup,x,y);
f.close();
ifstream f2("regiuni.in");
f2>>n>>m;
Lista q,del;
LG ug1;
for(i=1;i<=n;i++)
	{
	f2>>a>>b>>c;//g<<a<<" "<<b<<" "<<c<<"\n";
	nrgn=0;
	ug1=ug;
	for(grup=pg;grup!=ug1->urm;grup=grup->urm)
		//if(G[j].p!=G[j].u)
			{
			gasit=0;
			Z=a*grup->G.p->pct.x+b*grup->G.p->pct.y+c;
			for(q=grup->G.p->dr;q;)
				{
				if(Z*(a*q->pct.x+b*q->pct.y+c)<0)
					{
					if(!gasit)gasit=1,nrgn++;
					adauga(ug,q->pct.x,q->pct.y);
					del=q;
					q=q->dr;
					sterge(del,j);
					}
				else q=q->dr;
				}
			}
	nrg+=nrgn;
	//afisare();g<<"\n";
	}
g<<nrg<<"\n";
f2.close();
g.close();
return 0;
}