Cod sursa(job #49976)

Utilizator megabyteBarsan Paul megabyte Data 6 aprilie 2007 18:04:42
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <list>
#include <string>
#include <iterator>
#define INF "regiuni.in"
#define OUF "regiuni.out"
#define NMAX 1024
#define LMAX 1024 
#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,nr,ko,dim,sel;
	int use[LMAX]={0};
        
	vector<int> gr[LMAX],st,dr;
	vector<int>::iterator ti;
	list<int> next;
	list<int>::iterator it;
	
	muchie ed[NMAX];
	point pt[NMAX];

	fscanf(in,"%d %d",&n,&m);
	sel=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[1].pb(i);use[i]=0;next.pb(i);
	}
        use[1]=1;next.pop_front();it=next.begin();
	for(i=1;i<=n;i++)
	{
	    	
	        for(j=1;j<=m;j++)	
		{
		    if(use[j]==i)
		    {
//			nr=0;ko=0;
			for(k=0;k<gr[j].size();k++)
			{
				x=pt[gr[j][k]].x;y=pt[gr[j][k]].y;
				if(ed[i].a*x+ed[i].b*y+ed[i].c>0) dr.pb(gr[j][k]);
				else st.pb(gr[j][k]);
			}
                        use[j]=0;gr[j].clear();
			next.pb(j);
			if(!st.empty())
			{
				sel=(*it);it++;
			       	next.pop_front();
				gr[sel]=st;use[sel]=i+1;
				st.clear();
			}
			if(!dr.empty())
			{
				sel=(*it);it++;
				next.pop_front();
				gr[sel]=dr;use[sel]=i+1;
				dr.clear();
			}

		     }
		}
	}
        
	nr=0;
//	printf("%d",gr[4].size());
	for(i=1;i<=m;i++)
	{
		if(!gr[i].empty())
		{ 
		
		nr++;
		dim=gr[i].size();
		for(j=0;j<dim;j++) printf("%d ",gr[i][j]);
		printf("\n");
		
		}
	}
	fprintf(out,"%d",nr);
	fclose(in);fclose(out);
	return 0;
}