Cod sursa(job #2008379)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 6 august 2017 13:44:16
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define VAL 1005
#define MOD1 666013
#define MOD2 91121

using namespace std;

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

int N, M, i, j;
int A[VAL], B[VAL];
int C[VAL], X, Y;
int P1[VAL], P2[VAL];
int S1, S2, ANS;
vector < pair <int, int> > V;

int main()
{
    fin >> N >> M;
    P1[0]=P2[0]=1;
    for (i=1; i<=N; i++)
    {
        fin >> A[i] >> B[i] >> C[i];
        P1[i]=P1[i-1]*2;
        if (P1[i]>=MOD1)
          P1[i]-=MOD1;
        P2[i]=P2[i-1]*2;
        if (P2[i]>=MOD2)
          P2[i]-=MOD2;
    }
    V.push_back(make_pair(-1, -1));
    for (i=1; i<=M; i++)
    {
        fin >> X >> Y;
        S1=S2=0;
        for (j=1; j<=N; j++)
        {
            if (A[j]*X+B[j]*Y+C[j]>0)
            {
                S1+=P1[j-1];
                S2+=P2[j-1];
                if (S1>MOD1)
                  S1-=MOD1;
                if (S2>MOD2)
                  S2-=MOD2;
            }
        }
        V.push_back(make_pair(S1, S2));
    }
    sort(V.begin(), V.end());
    for (i=1; i<=M; i++)
      if (V[i]!=V[i-1])
        ANS++;
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}