Cod sursa(job #560713)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 18 martie 2011 17:29:05
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h> 
#include<algorithm>
#define min(a,b) ((a<b) ? a:b)
using namespace std;

struct dreapta
{
	int aa,bb,cc;
};

struct punct
{
	int x,y,gr;
};

int k,i,j,n,m,grupe; 
dreapta a[1005];
punct b[1005];

int ecuatie(punct X1,punct X2,int A,int B,int C)
{
	int s1,s2;
	if (A*X1.x+B*X1.y+C>0) s1=1;
		else s1=-1;
	if (A*X2.x+B*X2.y+C>0) s2=1;
		else s2=-1;
	if (s1==s2) return 0;
		else return 1;
}

inline bool cmp(const punct &aa,const punct &bb)
{
	return (aa.gr<bb.gr);
}

int main() 
{
	freopen("regiuni.in","r",stdin); 
	freopen("regiuni.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].aa,&a[i].bb,&a[i].cc);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&b[i].x,&b[i].y);
		b[i].gr=1;
	}
	
	for (i=1;i<=n;i++)
	{
		for (j=2;j<=m;j++)
			if (b[j].gr==b[j-1].gr)
				if (ecuatie(b[j],b[j-1],a[i].aa,a[i].bb,a[i].cc))
					b[j-1].gr++;
		grupe=1;
		for (j=2;j<=n;j++)
			if (b[j].gr!=b[j-1].gr)
			{
				grupe++;
				b[j].gr=grupe;
			}
		sort(b+1,b+n+1,cmp);
	}
	printf("%d\n",grupe);	

	return 0;
}