Cod sursa(job #46901)

Utilizator ionel71089lescai ionel ionel71089 Data 3 aprilie 2007 10:35:10
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 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;
int n,m,nrg=1,Z;
Grup G[1001];
Dreapta d[1001];
void adauga(int i,int x,int y)
	{
	Lista nou=new _lista;
	nou->pct.x=x,nou->pct.y=y;nou->st=nou->dr=NULL;
	if(G[i].p==NULL)
		G[i].p=G[i].u=nou;
	else
		nou->st=G[i].u,G[i].u->dr=nou,G[i].u=nou;
	}
void sterge(Lista &del,int i)
	{
	if(del==G[i].p)
		{
		G[i].p=G[i].p->dr;
		G[i].p->st=NULL;
		delete del;
		return;
		}
	if(del==G[i].u)
		{
		G[i].u=G[i].u->st;
		G[i].u->dr=NULL;
		delete del;
		return;
		}
	del->st->dr=del->dr;
	del->dr->st=del->st;
	delete del;
	}
//void afisare()
//	{
//	int i;
//	Lista j;
//	for(i=1;i<=nrg;i++,g<<"\n")
//		{
//		g<<i<<":";
//		for(j=G[i].p;j;j=j->dr)
//			g<<"("<<j->pct.x<<" "<<j->pct.y<<")";
//		}
//	}
int main()
{
int i,j,x,y,nrgn,gasit;
f>>n>>m;
for(i=1;i<=n;i++)
	f>>d[i].a>>d[i].b>>d[i].c;
for(i=1;i<=m;i++)
	f>>x>>y,adauga(1,x,y);
Lista q,del;
for(i=1;i<=n;i++)
	{
	nrgn=0;
	for(j=1;j<=nrg;j++)
		if(G[j].p!=G[j].u)
			{
			gasit=0;
			Z=d[i].a*G[i].p->pct.x+d[i].b*G[i].p->pct.y+d[i].c;
			for(q=G[j].p->dr;q;)
				{
				if(Z*(d[i].a*q->pct.x+d[i].b*q->pct.y+d[i].c)<0)
					{
					if(!gasit)gasit=1,nrgn++;
					adauga(nrg+nrgn,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;
return 0;
}