Cod sursa(job #88237)

Utilizator blasterzMircea Dima blasterz Data 30 septembrie 2007 22:24:32
Problema Regiuni Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
using namespace std;
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 1001
#define pb push_back
#define sh short
vector<sh>m[maxn];

sh int a[maxn], b[maxn], c[maxn],x[maxn],y[maxn];
int M, N;

void read()
{
	freopen("regiuni.in","r",stdin);
	scanf("%d %d\n", &M, &N);
	int i;
	for(i=1;i<=M;++i) scanf("%d %d %d\n", &a[i], &b[i], &c[i]);
	for(i=1;i<=N;++i) scanf("%d %d\n", &x[i], &y[i]);
}

inline int oki(sh int x, sh int y,  sh int a, sh int b, sh int c)
{
	int t=a*x+b*y+c;
	//if(t==0)return 0;
	if(t<=0) return 0;
	return 1;
}


void solve()
{
	int i, j,k, Nr=1,Nr2, n;
	vector<sh>p, q;
	p.reserve(maxn+1);
	q.reserve(maxn+1);
	for(i=1;i<=N;++i) m[1].pb(i);
	
	
	for(i=1;i<=M;++i)
	{	Nr2=Nr;
		for(j=1;j<=Nr;++j)
			if(m[j].size())
			{
				n=m[j].size();
				p.clear();
				q.clear();
				for(k=0;k<n;++k)
					if(oki(x[m[j][k]], y[m[j][k]], a[i], b[i], c[i])) 
						p.pb(m[j][k]);
					else q.pb(m[j][k]);
				if(p.size()==m[j].size()) ;
				else if(q.size()==m[j].size());
				else
				{
					m[j].clear();
					m[j]=p;
					m[++Nr2]=q;
				}
			}
			Nr=Nr2;
	}

//printf("%d\n", Nr);
Nr2=0;
for(i=1;i<=Nr;++i) if(m[i].size()) ++Nr2; 
printf("%d\n", Nr2);
}


int main()
{
	freopen("regiuni.out","w",stdout);
	read();
	solve();
	return 0;
}