Cod sursa(job #88342)

Utilizator blasterzMircea Dima blasterz Data 1 octombrie 2007 19:14:16
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
using namespace std;
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#define maxn 1001
#define pb push_back
#define sh short
//vector<sh>m[maxn];
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);
  sh p[maxn],q[maxn], np=0, nq=0;

  m[1]=(sh*)realloc(m[1], sizeof(sh)*(N+1));

  for(i=1;i<=N;++i) m[1][++m[1][0]]=i;  
	
  for(i=1;i<=M;++i)
    {	
      Nr2=Nr;
      for(j=1;j<=Nr;++j)
	if(m[j][0])
	  {
	    n=m[j][0];
	    // p.clear();
	    //q.clear();
	    np=nq=0;

	    for(k=1;k<=n;++k)
	      if(oki(x[m[j][k]], y[m[j][k]], a[i], b[i], c[i])) 
		p[++np]=m[j][k];
	      else q[++nq]=m[j][k];

	    if(np==n || nq==n);
	    else
	      {
		m[j]=(sh*)realloc(m[j], sizeof(sh)*(np+1));
		m[++Nr2]=(sh*)realloc(m[Nr2], sizeof(sh)*(nq+1));
		m[j][0]=m[Nr2][0]=0;
		for(k=1;k<=np;++k) m[j][++m[j][0]]=p[k];
		for(k=1;k<=nq;++k) m[Nr2][++m[Nr2][0]]=q[k];

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


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