Cod sursa(job #39775)

Utilizator victorsbVictor Rusu victorsb Data 26 martie 2007 22:44:53
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 1024
#define a first
#define b second.first
#define c second.second
#define x first
#define y second
#define pb push_back
#define sz size()

int n, m, ct;
pair<int, pair<int, int> > dr[Nmax];
pair<int, int> punct[Nmax];
vector< vector<int> > list1, list2;
vector<int> v1, v2;

void citire()
{
    int i;
    
    scanf("%d %d\n", &n, &m);
    
    for (i = 1; i <= n; ++i)
        scanf("%d %d %d\n", &dr[i].a, &dr[i].b, &dr[i].c);
    
    for (i = 1; i <= m; ++i)
        scanf("%d %d\n", &punct[i].x, &punct[i].y);
}

void solve()
{
    int i;
    typeof(list2.begin()) it1;
    typeof(list2[0].begin()) it2;
    
    list1.resize(1);
    
    for (i = 1; i <= m; ++i)
        list1[0].pb(i);
    
    for (i = 1; i <= n; ++i)
    {
        list2 = list1;
        list1.clear();
        
        for (it1 = list2.begin(); it1 != list2.end(); ++it1)
        {
            v1.clear();
            v2.clear();
            
            for (it2 = it1 -> begin(); it2 != it1 -> end(); ++it2)
                if (dr[i].a * punct[*it2].x + dr[i].b * punct[*it2].y + dr[i].c > 0)
                    v1.pb(*it2);
                else
                    v2.pb(*it2);
            
            if (!v1.empty())
                list1.pb(v1);
            if (!v2.empty())
                list1.pb(v2);
        }
    }
    
    printf("%d\n", list1.sz);
}

int main()
{
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);
    citire();
    solve();
    return 0;
}