Cod sursa(job #482042)

Utilizator andra23Laura Draghici andra23 Data 2 septembrie 2010 14:03:01
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<cstdio>
#define maxn 1010

using namespace std;

int da[maxn], db[maxn], dc[maxn];
int pa[maxn], pb[maxn];
int v[maxn], c[maxn], s[maxn];

int main(){
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);
    int m, n;
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        scanf("%d%d%d", &da[i], &db[i], &dc[i]);
    for (i = 1; i <= m; i++)
        scanf("%d%d", &pa[i], &pb[i]);
    
    int gr = 1, x;
    c[1] = m;
    for (i = 1; i <= m; i++)
        v[i] = 1;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= m; j++){
            if (da[i]*pa[j]+db[i]*pb[j]+dc[i] < 0){
                s[v[j]]++;
                v[j] = -v[j];
            } 
        }
        x = gr;
        for (j = 1; j <= x; j++)
            if (s[j] > 0) {
                if (s[j] == c[j])
                    s[j] = 0;
                else {
                    gr++;
                    c[j] = c[j] - s[j];
                    c[gr] = s[j]; 
                    s[j] = gr;    
                }    
            }
        for (j = 1; j <= m; j++)
            if (v[j] < 0){
                v[j] = -v[j];
                if (s[v[j]] != 0)
                    v[j] = s[v[j]];
            }
        for (j = 1; j <= gr; j++)
            s[j] = 0;         
    }
    
    printf("%d\n",gr);
    
    return 0;
}