Cod sursa(job #37518)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 25 martie 2007 10:42:58
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.18 kb
#include<stdio.h>

int n, m, reg[1024], rang[1024], uz[1024];
struct dreapta {int a, b, c;} d[1024];
struct punct { int x, y; } p[1024];

int multime(int x)
{
  if( x!=reg[x]) reg[x]= multime( reg[x]);
  return reg[x];
}

void reuneste(int i, int j)
{
  i= multime(i);
  j= multime(j);

  
  if( rang[i] < rang[j])
    reg[i]= reg[j];
  else reg[j]= reg[i];

  if( rang[i]== rang[j]) rang[i]++;
}

void solve()
{
  for(int i=1; i<=m; ++i)
    for(int j=1; j<=m; ++j) if( multime(i)!=multime(j)) {
      int k=0;
      while( ++k<=n && (d[k].a *p[i].x + d[k].b* p[i].y + d[k].c)*( d[k].a* p[j].x + d[k].b*p[j].y + d[k].c)>0 ) ;
      if( k==n+1) reuneste(i, j);

    }
}

void verif()
{
  int nr=0;
  for(int i=1; i<=m; ++i) if( !uz[ reg[i]]) {
    uz[reg[i]]=1;
    nr++;
  }

  freopen("regiuni.out","w",stdout);
  printf("%d\n",nr);
}

void init()
{
  for(int i=1; i<=m; ++i) reg[i]=i;
}

int main()
{
  freopen("regiuni.in","r",stdin);
  scanf("%d %d",&n, &m);
  for(int i=1; i<=n; ++i) scanf("%d %d %d",&d[i].a, &d[i].b, &d[i].c);
  for(int i=1; i<=m; ++i) scanf("%d %d",&p[i].x, &p[i].y);

  init();
  solve();
  verif();

  return 0;
}