Cod sursa(job #37432)

Utilizator sandyxpSanduleac Dan sandyxp Data 25 martie 2007 09:29:37
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.05 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define FIN "regiuni.in"
#define FOUT "regiuni.out"
#define MAXN 1000

struct dr { int a, b, c; } D[MAXN];
struct punct { int x, y; } A[MAXN];
struct elem { elem *r[2]; } *start = new elem;

int n, m, grup=0;

void rez() 
{
    int i, j, k, nou;
    memset(start,0,sizeof(start));
    elem *p;
    for (i=0; i<m; ++i) {
        p = start;
        for (j=0; j<n; ++j) {
            k = (D[j].a*A[i].x + D[j].b*A[i].y + D[j].c > 0);
            if (!p->r[k]) {
                p->r[k] = new elem;
                memset(p->r[k], 0, sizeof(elem));
                nou = 1;
            } else { nou = 0; }
            p = p->r[k];
        }
        if (nou) ++grup;
    }

    printf("%d\n", grup);
}

void citire()
{
    int i;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d\n", &n, &m);
    for (i=0; i<n; ++i)
        scanf("%d %d %d", &D[i].a, &D[i].b, &D[i].c);
    for (i=0; i<m; ++i)
        scanf("%d %d", &A[i].x, &A[i].y);
}


int main()
{
    citire();
    rez();
    return 0;
}