Cod sursa(job #40504)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 27 martie 2007 14:33:45
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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];
int wh[NMAX], list[NMAX], nr[2 * NMAX], poz[2 * NMAX], nwh[NMAX];

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++)
     wh[i] = 0, list[i] = i;
}

void solve()
{
	int i, j, a, b, c, z, x, y, bck = 0, ok;

     for(i = 0; i < N; i++)
     {
     	a = D[i].a, b = D[i].b, c = D[i].c;
          bck = 0;
		memset(nr, 0, sizeof(nr));
          for(z = 0; z < M;)
          {
          	ok = 0;
	          for(j = z; j < M && wh[list[j]] == wh[list[z]]; j++)
	          {
	          	x = V[list[j]].x, y = V[list[j]].y;
				if(a * x + b * y + c <= 0)
                    nwh[list[j]] = bck, nr[bck]++;
	               else
                    nwh[list[j]] = bck + 1, ok = 1, nr[bck + 1]++;
	          }
               poz[bck] = z, poz[bck + 1] = z + nr[bck];
               bck += ok + 1;
               z = j;
          }
          for(j = 0; j < M; j++)
		list[poz[nwh[j]]++] = j;
          memcpy(wh, nwh, sizeof(wh));
     }
     int rez = 0;
     
     for(i = 0; i < M - 1; i++)
	if(wh[list[i]] != wh[list[i + 1]])
     rez++;
     printf("%d\n", rez + 1);
}