Cod sursa(job #560736)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 18 martie 2011 17:37:01
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using  namespace std;
struct punct
{
	int x,y,g,i;
}p[1001];
struct dreapta
{
	int a,b,c;
}d[1001];
int m,n,i,j,q,k,cnt/*,g[1001]*/,w,nr;
bool o[1191];
inline int f(int a,int b, int c, int x ,int y)
{
	if(b==0)
	{
		float xd=-(float)(c/a);
		if(x<xd)return -1;
		return 1;
	}
	float dy =-(float)((a*x+c)/b);
	if(y>dy)return 1;
	return -1;
}
bool cmp(punct x,punct y)
{
	return (x.g==y.g ? 0 : x.g<y.g);
}
int main()
{
	freopen("regiuni.in","r",stdin);
	freopen("regiuni.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(i=0;i<m;i++)scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
	for(i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].i=i+1;
	cnt=0;
	for(k=0;k<m;k++)
	{
		i=0;
		while(i<n)
		{
			j=i;
			while( p[i].g==p[j+1].g && j+1<n ) j++;
			for(q=i;q<=j;q++)
			{
				w=f(d[k].a,d[k].b,d[k].c,p[q].x,p[q].y);
				if(w==1)p[q].g=cnt+1;
			}
			cnt++;
			i=j+1;
		}
		sort(p,p+n,cmp);
	}
	nr=0;
	for(i=0;i<n;i++)if(!o[p[i].g])nr++,o[p[i].g]=1;
	printf("%d",nr);
	return 0;
}