Cod sursa(job #1787079)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 24 octombrie 2016 09:10:31
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <utility>
#include <vector>

#define x first
#define y second

#define MAXN 1000
#define MAXM 1000

int a[MAXM], b[MAXM], c[MAXM];

std::vector <std::pair <int, int> > v[MAXN+1];

int main(){
    int k, n, m, x, y, t;
    bool corect, check;
    FILE *fin, *fout;
    fin=fopen("regiuni.in", "r");
    fout=fopen("regiuni.out", "w");
    fscanf(fin, "%d%d", &m, &n);
    for(int i=0; i<m; i++)
        fscanf(fin, "%d%d%d", &a[i], &b[i], &c[i]);
    k=1;
    for(int i=1; i<=n; i++){
        fscanf(fin, "%d%d", &x, &y);
        v[0].push_back(std::make_pair(x, y));
    }
    for(int i=0; i<m; i++){
        t=k;
        for(int j=0; j<k; j++){
            corect=(a[i]*v[j][0].x+b[i]*v[j][0].y+c[i])>0;
            int p=1;
            while(p<(int)v[j].size()){
                check=(a[i]*v[j][p].x+b[i]*v[j][p].y+c[i])>0;
                if(corect!=check){
                    v[t].push_back(v[j][p]);
                    v[j][p]=v[j].back();
                    v[j].pop_back();
                    p--;
                }
                p++;
            }
            if(v[t].size())
                t++;
        }
        k=t;
    }
    fprintf(fout, "%d\n", k);
    fclose(fin);
    fclose(fout);
    return 0;
}