Cod sursa(job #44896)

Utilizator sandyxpSanduleac Dan sandyxp Data 31 martie 2007 19:45:30
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <string.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 { short span; elem *r; } *start = new elem;

int n, m;
int Reg[MAXN], regs; // regiuni
int Reg2[MAXN];
// Regspan = cate elemente are acea regiune
//  pe poz i in sirul de regiuni (Reg[]) se afla punctul Reg[i]

void rez() 
{
    int i, j, k, peste, st1;
    elem *p;
    for (i=0; i<m; ++i)
        Reg[i] = i;
    regs = 1;
    start->r = new elem; start->r->span = m; start->r->r = 0;

    for (i=0; i<n; ++i) {
        // luam fiecare regiune
        for (p=start->r, j = 0; p; p = p->r, j += k) {
            for (peste=0, k=0; k < p->span; ++k)
                peste += (D[i].a*A[Reg[j+k]].x + D[i].b*A[Reg[j+k]].y + D[i].c > 0);
            if (peste == 0 || peste == p->span) continue;
            // Grupul este divizat
            ++ regs;
            elem *temp = new elem;
            temp -> r = p->r;
            p->r = temp;

            memcpy(Reg2, &Reg[j], p->span * sizeof(int));
            for (st1 = 0, k=0; k < p->span; ++k)
                if (D[i].a*A[Reg2[k]].x + D[i].b*A[Reg2[k]].y + D[i].c > 0)
                    Reg[j+(st1++)] = Reg2[k];
                else Reg[j+(peste++)] = Reg2[k];
            p->span = st1; // cate sunt la inceput
            p->r->span = k - st1;
            p = p->r;
        }
    }
    printf("%d\n", regs);
}

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