Cod sursa(job #42581)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 29 martie 2007 12:38:27
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 1010
#define pb push_back

int n,m,sol;
int a[maxn],b[maxn],c[maxn],x[maxn],y[maxn];
vector <int> v;

void solve(int k,vector <int> v)
{
     if (k>n) sol++;
     else {
             vector <int> p,q;
             int i;
             p.clear();
             q.clear();
             
             for (i=0;i<v.size();i++)
               if (a[k]*x[v[i]]+b[k]*y[v[i]]+c[k]<0) p.pb(v[i]);
               else q.pb(v[i]);
               
             if (p.size()>0) solve(k+1,p);
             if (q.size()>0) solve(k+1,q);
          }  
}

int main()
{
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);
    
    scanf("%d %d ",&n,&m);
    
    int i;
    
    for (i=1;i<=n;i++) scanf("%d %d %d ",&a[i],&b[i],&c[i]);
    
    for (i=1;i<=m;i++) scanf("%d %d ",&x[i],&y[i]);
    
    for (i=1;i<=m;i++) v.pb(i);
    
    solve(1,v);
    
    printf("%d\n",sol);
    
    return 0;
}