Cod sursa(job #40710)

Utilizator victorsbVictor Rusu victorsb Data 27 martie 2007 17:49:02
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 1001
#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<short, pair<short, short> > dr[Nmax];
pair<short, short> punct[Nmax];
vector< vector<unsigned int> > list;
vector<unsigned int> v;

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

void solve()
{
    int i, j, k;
    
    list.resize(m);
    
    for (i = 1; i <= m; ++i)
    {
        k = -1;
        v.clear();
        v.resize(32);
        for (j = 0; j < n; ++j)
        {
            if (j % 32 == 0)
                ++k;
            
            if (dr[j + 1].a * punct[i].x + dr[j + 1].b * punct[i].y + dr[j + 1].c < 0)
                v[k] += 1 << (j % 32);
        }
        list[i - 1] = v;
    }
    
    typeof(list.begin()) it;
    sort(list.begin(), list.end());
    it = unique(list.begin(), list.end());
    list.erase(it, list.end());
    
    printf("%d\n", list.sz);
}

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