Cod sursa(job #2201829)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 6 mai 2018 11:40:04
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>

#define MOD1 666013
#define MOD2 666019
using namespace std;

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

int n, m;

struct element{
    int hash1, hash2;
}H[1005];

struct drepte{
    int a, b, c;
}dr[1005];

int Hash(int x, int y, int MOD){ /// 1 = < 0 si 2 = >0
    long long rez = 0;
    for(int i = 1; i <= n; ++i){
        short faranume = dr[i].a * x + dr[i].b * y + dr[i].c;
        if(faranume < 0)
            rez = rez * 3 + 1;
        else rez = rez * 3 + 2;

        rez %= MOD;
    }

    return rez;
}

inline bool cmp(element a, element b){
    if(a.hash1 == b.hash1)
        return a.hash2 < b.hash2;
    return a.hash1 < b.hash1;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i)
        fin >> dr[i].a >> dr[i].b >> dr[i].c;

    for(int i = 1; i <= m; ++i){
        int xx, yy;
        fin >> xx >> yy;

        H[i].hash1 = Hash(xx, yy, MOD1);
        H[i].hash2 = Hash(xx, yy, MOD2);
    }

    sort(H + 1, H + m + 1, cmp);

    int nrGrupe = 1;
    for(int i = 2; i <= m; ++i)
        if((H[i].hash1 != H[i - 1].hash1) || (H[i].hash2 != H[i - 1].hash2))
            ++nrGrupe;

    fout << nrGrupe << '\n';
    return 0;
}