Cod sursa(job #37624)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 25 martie 2007 11:29:38
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 0.77 kb
#include<stdio.h>

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

void solve()
{
  int max=1, max2=1;
  for(int k=1; k<=n; ++k) {
    for(int i=1; i<=m; ++i) if( d[k].a*p[i].x + d[k].b*p[i].y +d[k].c <0) {
      reg[i]+=max;
      if( reg[i] > max2) max2= reg[i];
    }
    max= ++max2;
  }

  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);
  
}


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);

  solve();


  return 0;
}