Cod sursa(job #53982)

Utilizator filipbFilip Cristian Buruiana filipb Data 23 aprilie 2007 21:14:45
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#define NMax 1005

int N, M, A[NMax], B[NMax], C[NMax], X[NMax], Y[NMax];

int reg[NMax], sep[NMax], spec[NMax], t_plus[NMax], nr = 0;

int semn(int A, int B, int C, int x, int y)
{
    int E = A * x + B * y + C;

    if (E < 0) return -1;
    if (E > 0) return +1;
    return 0;
}

int main(void)
{
    int i, j;
    
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);

    scanf("%d %d", &N, &M);

    for (i = 1; i <= N; i++)
        scanf("%d %d %d", &A[i], &B[i], &C[i]);
    for (i = 1; i <= M; i++)
        scanf("%d %d", &X[i], &Y[i]);

    for (i = 1; i <= M; i++) reg[i] = 1; nr = 1;

    for (i = 1; i <= N; i++)
    {
        for (j = 1; j <= nr; j++) sep[j] = t_plus[j] = spec[j] = 0;
        for (j = 1; j <= M; j++) sep[reg[j]]++;
        
        for (j = 1; j <= M; j++)
            t_plus[reg[j]] += (semn(A[i], B[i], C[i], X[j], Y[j]) == 1);

        for (j = 1; j <= M; j++)
            if (t_plus[reg[j]] && t_plus[reg[j]] < sep[reg[j]])
            {
                // dreapta imparte in doua zona reg[j]
                if (semn(A[i], B[i], C[i], X[j], Y[j]) == -1)
                {
                    if (!spec[reg[j]]) spec[reg[j]] = (++nr);
                    reg[j] = spec[reg[j]];
                }
            }
        
    }

    printf("%d\n", nr);

    return 0;    
}