Cod sursa(job #3209403)

Utilizator zavragiudavid dragoi zavragiu Data 2 martie 2024 12:50:16
Problema Regiuni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
using namespace std;

ifstream fin("regiuni.in");
ofstream fout("regiuni.out");
struct Coduri
{
    int c1, c2;
};
int a[1001], b[1001], c[1001];
int n, m;
Coduri t[1001];

bool Compar(Coduri A, Coduri B)
{
    if (A.c1 == B.c1)
        return A.c2 < B.c2;
    return A.c1 < B.c1;
}

/**
ret. valoarea 0 daca punctul (x,y) se afla
  in semiplanul -
ret. valoarea 1 daca punctul (x,y) se afla
  in semiplanul +
*/
int Semn(int a, int b, int c, int x, int y)
{
    if (a*x + b*y + c < 0) return 0;
    return 1;
}

int main()
{
    int i, j, x, y, val;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        fin >> a[i] >> b[i] >> c[i];
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        t[i].c1 = t[i].c2 = 0;
        for (j = 1; j <= n; j++)
        {
            val = Semn(a[j],b[j],c[j],x,y);
            t[i].c1 = (t[i].c1 * 2 + val) % P;
            t[i].c2 = (t[i].c2 * 2 + val) % Q;
        }
    }
    sort(t + 1, t + m + 1, Compar);
    /**
    1 1 3 5 7 7 7 9
    1 1 5 2 6 6 8 4
    */
    x = 1;
    for (i = 2; i <= m; i++)
        if (t[i].c1 != t[i-1].c1 ||
            t[i].c2 != t[i-1].c2) x++;
    fout << x << "\n";
    return 0;
}