Cod sursa(job #1466151)

Utilizator enedumitruene dumitru enedumitru Data 28 iulie 2015 18:17:02
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<map>
#define ll long long
#define mk make_pair
using namespace std;
ifstream fi("regiuni.in"); ofstream fo("regiuni.out");
int a[1001],b[1001],c[1001],x[1001],y[1001];
map <pair<int,int>,bool> s;
int main(void)
{   int n,m,i,nr=0;
    fi>>n>>m;
    for(i=1;i<=n;++i) fi>>a[i]>>b[i]>>c[i];
    for(i=1;i<=m;++i) fi>>x[i]>>y[i];
    for(i=1;i<=m;++i)
    {   int r1=0,r2=0;
        for(int j=1;j<=n;++j)
        {   ll v=1ll*a[j]*x[i]+1ll*b[j]*y[i]+c[j];
            v=(v>0);
            r1=(r1*10+v)%666013; r2=(r2*10+v)%997;
        }
        if (!s.count(mk(r1,r2))) {++nr; s[mk(r1,r2)]=1;}
    }
    fo<<nr<< '\n'; fo.close(); return 0;
}
/*
Cel mai simplu poti sa consideri semnele ca fiind cifre iar sirul un numar in baza 2
(de exemplu semnul -1 corespunde lui 0 si +1 lui 1) si acum nu ai decat de facut un hash (rabin-karp),
adica calculezi numarul asta % un numar prim mare. Daca esti paranoic poti considera mai multe numere prime mari si calculezi restul pentru toate
*/