Cod sursa(job #1594534)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 9 februarie 2016 15:56:41
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n, m, i, j, ok, nr, sum;
int a[1005][1005 / 30 + 5], v[1005];
pair<int, int> p[1005];
struct dreapta{
    int a;
    int b;
    int c;
};
dreapta d[1005];
ifstream fin("regiuni.in");
ofstream fout("regiuni.out");
int cmp(int x, int y){
    for(int  i = 0; i <= n / 30; i++){
        if(a[x][i] != a[y][i]){
            return a[x][i] < a[y][i];
        }
    }
    return a[x][n / 30] < a[y][n / 30];
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        fin>> d[i].a >> d[i].b >> d[i].c;
    }
    for(i = 1; i <= m; i++){
        v[i] = i;
        fin>> p[i].x >> p[i].y;
        for(j = 1; j <= n; j++){
            sum = p[i].x * d[j].a + p[i].y * d[j].b + d[j].c;
            if(sum > 0){
                a[i][j / 30] += (1 << (j % 30));
            }
        }
    }
    sort(v + 1, v + m + 1, cmp);
    nr = 1;
    for(i = 2; i <= m; i++){
        ok = 1;
        for(j = 0; j <= n / 30; j++){
            if(a[ v[i] ][j] != a[ v[i - 1] ][j]){
                ok = 0;
            }
        }
        if(ok == 0){
            nr++;
        }
    }
    fout<< nr <<"\n";
    return 0;
}