Cod sursa(job #702473)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 1 martie 2012 22:00:00
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define pb push_back
#define Nmax 1009

struct dreapta
{
	short A,B,C;
};

using namespace std;

short j,q,k,nr,ok,n,m,i,grupa[Nmax];
pair<short,short> a[Nmax];
dreapta b[Nmax];
vector<short> sol[Nmax];

int semn(dreapta X, pair<short,short> p)
{
	if (p.x*X.A+p.y*X.B+X.C>=0) return 1;
	return -1;
}

int main()
{
	freopen("regiuni.in","r",stdin);
	freopen("regiuni.out","w",stdout);
	
	scanf("%hd%hd",&m,&n);
	
	for (i=1;i<=m;i++)
		scanf("%hd%hd%hd",&b[i].A,&b[i].B,&b[i].C);
		
	for (i=1;i<=n;i++)
	{
		scanf("%hd%hd",&a[i].x,&a[i].y);
		grupa[i]=1;
		sol[1].pb(i);
	}
	nr=1;	
	
	for (i=1;i<=m;i++)
		for (j=1;j<=nr;j++)
		{
			q=semn(b[i],a[sol[j][0]]);
			ok=0;
			nr++;
			
			for (k=1;k<sol[j].size();k++)
				if (semn(b[i],a[sol[j][k]])!=q)
				{
					ok=1;
					sol[nr].pb(sol[j][k]);
					sol[j].erase(sol[j].begin()+k);
					k--;
				}
			if (!ok) nr--;
		}
	printf("%hd\n",nr);
}