Cod sursa(job #2368072)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 5 martie 2019 13:38:50
Problema Regiuni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>
#define prim1 9973
#define prim2 8867

using namespace std;

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

struct dreapta
{
    short a, b, c;
}dr[1001];

int has1[1001], has2[1001], n, m;

inline int P(dreapta D, int x, int y)
{
    if (D.a * x + D.b * y + D.c < 0)
        return -1;
    return 1;
}

void Citire()
{
    int h1, h2;

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

    short x, y;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;

        h1 = h2 = 0;

        ///hashuiesc punctele perfect
        /// in functie de pozitia lor fata
        /// de fiecare dreapta

        ///hashingul perfect se foloseste
        /// pentru maparea unui set de valoro
        /// pe alt set de valori fara coliziuni
        for(int j = 1; j <= n; j++)
        {
            h1 = h1 * 10;
            h2 = h2 * 10;

            if(P(dr[j], x, y) < 0)
            {
                h1++;
                h2++;
            }
            else
            {
                h1 += 2;
                h2 += 2;
            }

            h1 = h1 % prim1;
            h2 = h2 % prim2;
        }

        has1[i] = h1;
        has2[i] = h2;
    }
}

void Rezolvare()
{
    bool gasit;
    int grupuri = 1;

    for(int i = 2; i <= m; i++)
    {
        gasit = 0;

        for(int j = 1; j < i && !gasit; j++)
            if(has1[j] == has1[i] && has2[j] == has2[i])
                gasit = 1;

        if(gasit == 0)
            grupuri++;
    }

    fout << grupuri << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}