Cod sursa(job #1737811)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 4 august 2016 21:07:47
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;
#define llu long long unsigned
#define ll long long
#define pb push_back
#define mp make_pair

string problemName = "regiuni";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());

const int N = 1005;

struct dr{
    int a,b,c;
}v[N];

struct pct{
    int x,y;
}p[N];

vector <int> group[N];

int main(){
    int n,m,i,cnt,CNT,j,k,x,y,gr,l,s;
    bool ok;
    fin>>n>>m;
    for(i = 1;i <= n;i++){
        fin>>v[i].a>>v[i].b>>v[i].c;
    }
    group[1].pb(m);
    for(i = 1;i <= m;i++){
        group[1].pb(i);
        fin>>p[i].x>>p[i].y;
    }
    CNT = 1;
    for(i = 1;i <= n;i++){
        cnt = CNT;
        for(j = 1;j <= CNT;j++){
            ok = false;
            x = p[group[j][1]].x;
            y = p[group[j][1]].y;
            if(v[i].a*x + v[i].b*y + v[i].c > 0){
                s = 1;
            }else{
                s = -1;
            }
            gr = group[j][0];
            for(k = 2;k <= group[j][0];k++){
                x = p[group[j][k]].x;
                y = p[group[j][k]].y;
                if(s * (v[i].a*x + v[i].b*y + v[i].c) < 0){
                    if(ok == false){
                        cnt++;
                        group[cnt].pb(0);
                        ok = true;
                    }
                    group[cnt][0]++;
                    group[cnt].pb(group[j][k]);
                    cerr<<group[j][k]<<' ';
                    gr--;
                    group[j][k] = -1;
                }
            }
            for(k = 2;k <= group[j][0];k++){
                if(group[j][k] == -1){
                    for(l = k+1;l <= group[j][0];l++){
                        if(group[j][l] != -1){
                            group[j][k] = group[j][l];
                            group[j][l] = -1;
                            k = l;
                            break;
                        }
                    }
                }
            }
            group[j].resize(gr+1);
            group[j][0] = gr;
        }
        CNT = cnt;
    }
    fout<<CNT;
    return 0;
}