Cod sursa(job #560707)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 18 martie 2011 17:27:20
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 1001

using namespace std;

typedef struct {int a; int b; int c;} dreapta;
typedef struct {int x; int y; int indgr;} punct;

punct p[NMAX];
dreapta d[NMAX];
int n,m,i,j,nrgrupe;

bool parte_dr(int idr, int ip)
{
	return( d[idr].a*p[ip].x + d[idr].b+p[ip].y + d[idr].c > 0 );
}

inline bool cmp(const punct &x, const punct &y)
{
	return (x.indgr < y.indgr);
}

int main()
{
	freopen("regiuni.in","r",stdin);
	freopen("regiuni.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
		scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
	for(i=0;i<m;i++)
		scanf("%d%d",&p[i].x,&p[i].y);
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
			if(parte_dr(i,j))
				++p[j].indgr;
		
		nrgrupe=1;
		for(j=1;j<m;j++)
			if(p[j].indgr != p[j-1].indgr)
			{
				++nrgrupe;
				p[j].indgr = nrgrupe;
			}
		
		sort(p,p+m,cmp);
	}
	
	printf("%d\n",nrgrupe);
	
	return 0;
}