Cod sursa(job #595194)

Utilizator SpiderManSimoiu Robert SpiderMan Data 11 iunie 2011 14:20:12
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
# include <cstdio>

const char *FIN = "regiuni.in", *FOU = "regiuni.out";
const int MAX = 1005 ;

int A[MAX], B[MAX], C[MAX], X[MAX], Y[MAX], dp[MAX], viz[MAX], cnt[MAX], region[MAX];
int N, M, solution = 1;

int signum (int A, int B, int C, int X, int Y) {
    int exp = A * X + B * Y + C;
    return (exp < 0 ? -1 : (exp > 0 ? 1 : 0)) ;
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d %d", &N, &M) ;
    for (int i = 1 ; i <= N; ++i)
        scanf ("%d %d %d", A + i, B + i, C + i);
    for (int i = 1; i <= M; ++i)
        scanf ("%d %d", X + i, Y + i), region[i] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= solution; ++j)
            dp[j] = viz[j] = cnt[j] = 0;
        for (int j = 1; j <= M; ++j) {
            ++cnt[region[j]];
            dp[region[j]] += signum (A[i], B[i], C[i], X[j], Y[j]) == 1;
        }
        for (int j = 1; j <= M; ++j) {
            if (dp[region[j]] && dp[region[j]] < cnt[region[j]]) {
                if (signum (A[i], B[i], C[i], X[j], Y[j]) == -1) {
                    if (viz[region[j]] == 0) viz[region[j]] = ++solution;
                    region[j] = viz[region[j]];
                }
            }
        }
    }
    fprintf (fopen (FOU, "w"), "%d", solution) ;
}