Cod sursa(job #38907)

Utilizator crawlerPuni Andrei Paul crawler Data 26 martie 2007 11:23:09
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <bitset>
#include <vector>

using namespace std;

struct dreapta
 {
  int a,b,c;
 } d[1001];

struct pct
 {
  int x,y;
 } p[1001];

 
bitset<1024> b[1001];

vector<int> a[1001];

int m, S;
char e[1001];

void DF(int nod)
 {
  if(e[nod])
   return ;

  int i;

  e[nod] = S;

  if(a[nod].size())
  for(i=0;i<a[nod].size();++i)
   DF(a[nod][i]);
 }


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

  int i,j,n;

  scanf("%d%d", &n,&m);

  for(i=1;i<=n;++i)
   scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);

  for(i=1;i<=m;++i)
   scanf("%d%d", &p[i].x, &p[i].y);

  for(i=1;i<=m;++i)
   for(j=1;j<=n;++j)
    if(d[j].a*p[i].x+d[j].b*p[i].y+d[j].c > 0)
     b[i][j] = 1;

  for(i=1;i<=m;++i)
   for(j=i+1;j<=m;++j)
     if( b[i] == b[j] )
      {
       a[i].push_back(j);
       a[j].push_back(i);
      }

  for(i=1;i<=m;++i)
   if(e[i] == 0)
    {
     ++S;
     DF(i);
    }


  printf("%d\n", S);

  return 0;
 }