Cod sursa(job #80329)

Utilizator cosminpdrfischer2004 cosminp Data 27 august 2007 13:56:44
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <vector>
#include <list>
#include <fstream>

using namespace std;

typedef struct point{
	int x, y;
} point;

typedef struct line{
	int a, b, c;
} line;


vector<point> p(500);
vector<list<int> > g(1);
vector<line> d(500);

int main()
{
	fstream f, go;
	int i, j, n, m, ng, ngg, sgn;
	point t;
	list<int>::iterator it;
	
	f.open("regiuni.in", ios :: in);
	f >> n >> m;
	
	for (i = 0; i < n; i++)
		f >> d[i].a >> d[i].b >> d[i].c;
	
	for (i = 0; i < m; i++)
	{
		f >> p[i].x >> p[i].y;
		g[0].push_back(i);
	}
	f.close();
	
	ng = ngg = 1;
	for (i = 0; i < n; i++)
	{
		for( j = 0; j < ng; j++)
		{
			list<int> l1, l2;
			it = g[j].begin();
			t = p[*it];
			sgn = d[i].a*(t.x) + d[i].b*(t.y) + d[i].c;
			for (it = g[j].begin(); it != g[j].end(); it++)
			{
				t = p[*it];
				if (sgn * (d[i].a*(t.x) + d[i].b*(t.y) + d[i].c) < 0)
					l1.push_back(*it);
				else l2.push_back(*it);
			}
			/*
			g[j].clear();
			for ( it = l2.begin(); it != l2.end(); it++)
				g[j].push_back(*it);
			
			if (!l1.empty()) 
			{
				
				for ( it = l1.begin(); it != l1.end(); it++)
					g[ngg].push_back(*it);
				ngg++;
			}
			*/
			g[j] = l2; 
			if (!l1.empty()) g.push_back(l1), ngg++;
		}
		ng = ngg;
	}
	
	go.open("regiuni.out", ios :: out);
	go << ng;
	go.close();
	
	return 0;
}