Cod sursa(job #40904)

Utilizator victorsbVictor Rusu victorsb Data 27 martie 2007 20:31:26
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 1001
#define a first
#define b second.first
#define c second.second
#define x first
#define y second

int n, m, ct;
pair<short, pair<short, short> > dr[Nmax];
pair<short, short> punct[Nmax];
unsigned int mat[Nmax][32], tmp[32];

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

int cmp(int A, int B)
{
    int i;
    
    for (i = 0; i < 32; ++i)
        if (mat[A][i] < mat[B][i])
            return 1;
        else if (mat[A][i] > mat[B][i])
            return -1;
    
    return 0;
}

void qsort(int st, int dr)
{
    int i, j, sch;
    
    i = st, j = dr;
    sch = (st + dr) / 2;
    
    do
    {
        while (cmp(i, sch) == 1)
            ++i;
        
        while (cmp(sch, j) == 1)
            --j;
        
        if (i <= j)
        {
            memcpy(tmp, mat[i], sizeof(tmp));
            memcpy(mat[i], mat[j], sizeof(tmp));
            memcpy(mat[j], tmp, sizeof(tmp));
            ++i, --j;
        }
    }
    while (i <= j);
    
    if (st < j) qsort(st, j);
    if (i < dr) qsort(i, dr);
}

void solve()
{
    int i, j, k, ct = 0;
    
    for (i = 1; i <= m; ++i)
    {
        k = -1;
        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)
                mat[i][k] += 1 << (j % 32);
        }
    }
    
    qsort(1, m);
    
    ct = 1;
    for (i = 2; i <= m; ++i)
        if (cmp(i, i -1))
            ++ct;
    
    printf("%d\n", ct);
}

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