Cod sursa(job #47487)

Utilizator megabyteBarsan Paul megabyte Data 3 aprilie 2007 19:14:35
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <list>
#include <string>
#define INF "regiuni.in"
#define OUF "regiuni.out"
#define NMAX 1024
#define LMAX 2048
#define pb push_back
using namespace std;

struct muchie
{
	int a,b,c;
};

struct point
{
	int x,y;
};



int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int i,j,k,x,y,n,m;
        int op,oldim,dim,nr,ko;
	char gone[LMAX]={0};
        
	list<int> gr[LMAX];
	list<int>::iterator it,del;
	
	muchie ed[NMAX];
	point pt[NMAX];

	fscanf(in,"%d %d",&n,&m);
	dim=1;
        for(i=1;i<=n;i++) fscanf(in,"%d %d %d",&ed[i].a,&ed[i].b,&ed[i].c);
	for(i=1;i<=m;i++) { fscanf(in,"%d %d",&pt[i].x,&pt[i].y);gr[dim].pb(i); }
        
	
	
	for(i=1;i<=n;i++)
	{
		oldim=dim;
		for(op=1;op<=oldim;op++)
		{
		    if(!gone[op])
		    {
			nr=0;ko=0;
			for(it=gr[op].begin();it!=gr[op].end();it++)
			{
				if(ko)
				{
					gr[op].erase(del);
					ko=0;
				}
				x=pt[(*it)].x;y=pt[(*it)].y;
				if(ed[i].a*x+ed[i].b*y+ed[i].c>0)
				{
					if(!nr)//grup nou
					{
						nr++;
						dim++;
					}
					gr[dim].pb(*it);
					ko=1;del=it;
				}
			}
			if(ko)
			{
				gr[op].erase(del);
				ko=0;
			}
			if(gr[op].empty()) gone[op]=1;
		     }
		}
	}
        
	nr=0;
	//printf("%d",dim);
	for(i=1;i<=dim;i++) if(!gone[i]) nr++;
	fprintf(out,"%d",nr);
	fclose(in);fclose(out);
	return 0;
}