Cod sursa(job #37767)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 25 martie 2007 12:28:05
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.72 kb
using namespace std;
#include<stdio.h>
#include<vector>

#define NMAX 1024

typedef struct t_d
{
	int a, b, c;
};
typedef struct t_v
{
	int x, y;
};

void read();
void solve();

int N, M, lim = 1;
t_d D[NMAX];
t_v V[NMAX];
vector<int> v[NMAX], A, B;

int main()
{
	freopen("regiuni.in", "r", stdin);
     freopen("regiuni.out", "w", stdout);

     read();
     solve();
	return 0;
}

void read()
{
	int i;
     
	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", &V[i].x, &V[i].y);
     for(i = 0; i < M; i++)
     v[0].push_back(i);
}

void solve()
{
	int i, j, a, b, c, z, x, y, newlim;

     for(i = 0; i < N; i++)
     {
     	a = D[i].a, b = D[i].b, c = D[i].c;
          newlim = lim;
          for(z = 0; z < lim; z++)
          {
          	A.clear();
               B.clear();
	          for(j = 0; j < v[z].size(); j++)
	          {
	          	x = V[v[z][j]].x, y = V[v[z][j]].y;
				if(a * x + b * y + c <= 0)
                    A.push_back(v[z][j]);
	               else
                    B.push_back(v[z][j]);
	          }
               v[z].clear();
               if(!A.empty())
               {
               	for(j = 0; j < A.size(); j++)
                    v[z].push_back(A[j]);
                    
                    if(!B.empty())
                    {
                    	for(j = 0; j < B.size(); j++)
	                    v[newlim].push_back(B[j]);
	                    newlim++;
                    }
               }
               else
               {
               	for(j = 0; j < B.size(); j++)
                    v[z].push_back(B[j]);
               }
          }
          lim = newlim;
     }
     printf("%d\n", lim);
}