Cod sursa(job #2010828)

Utilizator mariusn01Marius Nicoli mariusn01 Data 14 august 2017 14:48:52
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <bitset>
#define DIM 1010

using namespace std;

struct dreapta {
    int a;
    int b;
    int c;
};

dreapta v[DIM];
int n, m, i, sol, j, x, y;
bitset<DIM> a[DIM];
int b[DIM];

int f(int x, int y, int i) {
    return v[i].a * x + v[i].b * y + v[i].c;
}

int cmpCol(int i, int j) {
    for (int k=1;k<=n;k++) {
        if (a[k][i] < a[k][j])
            return -1;
        if (a[k][i] > a[k][j])
            return 1;
    }
    return 0;
}

int cmp(int i, int j) {
    return cmpCol(b[i], b[j]) < 0;
}

int main () {
    ifstream fin ("regiuni.in");
    ofstream fout("regiuni.out");

    fin>>n>>m;
    for (i=1;i<=n;i++) {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }
    int t;
    for (j=1;j<=m;j++) {
        fin>>x>>y;
        for (i=1;i<=n;i++) {
            a[i][j] = (t = (f(x, y, i) > 0 ? 0 : 1));
        }
    }

    for (i=1;i<=m;i++)
        b[i] = i;

    sort(b+1, b+m+1, cmp);
    sol = 1;
    for (i=2;i<=m;i++)
        if (cmpCol(b[i], b[i-1]) != 0)
            sol++;

    fout<<sol;
    return 0;
}