Cod sursa(job #482037)

Utilizator andra23Laura Draghici andra23 Data 2 septembrie 2010 13:56:33
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<fstream>
#define maxn 1010

using namespace std;

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

int main(){
    ifstream f("regiuni.in");
    ofstream g("regiuni.out");
    short m, n;
    int i, j;
    f>>n>>m;
    for (i = 1; i <= n; i++)
        f>>da[i]>>db[i]>>dc[i];
    for (i = 1; i <= m; i++)
        f>>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;         
    }
    
    g<<gr<<'\n';
    
    return 0;
}