Cod sursa(job #481725)

Utilizator andra23Laura Draghici andra23 Data 1 septembrie 2010 14:56:24
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<iostream>
#include<fstream>
#define maxn 1010

using namespace std;

struct dreapta {
    short a, b, c;
    dreapta() {}
    dreapta(short aa, short bb, short cc){
        a = aa;
        b = bb;
        c = cc;
    }
};

struct punct {
    short x, y;
    punct(){}
    punct(short a, short b){
        x = a;
        y = b;
    }
};

dreapta d[maxn];
punct p[maxn];
int v[maxn], c[maxn], s[maxn];

int main(){
    ifstream f("regiuni.in");
    ofstream g("regiuni.out");
    short m, n, a, b, cc;
    int i, j;
    f>>n>>m;
    for (i = 1; i <= n; i++){
        f>>a>>b>>cc;
        d[i] = dreapta(a, b, cc);
    }
    for (i = 1; i <= m; i++){
        f>>a>>b;
        p[i] = punct(a, b);
    }
    
    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 (d[i].a*p[j].x+d[i].b*p[j].y+d[i].c < 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;
}