Cod sursa(job #1073430)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 6 ianuarie 2014 11:07:43
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#define NMax 1024
#define MMax 1024
#define MOD 666013
#define X 13

using namespace std;

struct dreapta
{
    int a, b, c;
    dreapta() {}
    dreapta(const int _a, const int _b, const int _c)
    {
        a = _a, b = _b, c = _c;
    }
};
dreapta d[MMax];

int n, m;
int t[NMax];

inline int Det(const double x1, const double y1, const double x2, const double y2, const int x3, const int y3)
{
    // x1 y1 1
    // x2 y2 1
    // x3 y3 1
    if (x1*y2 + x3*y1 + x2*y3 - y2*x3 - y3*x1 - x2*y1 > 0)
        return 1;
    return 0;
}

inline int Side(const int a, const int b, const int c, const int x, const int y)
{
    /*
        a*x + b*y + c = 0
        x = 0 -> y = -c/b
        y = 0 -> x = -c/a
    */
    if (a == 0)
        return Det(0, -1.0 * c/b, 1, -1.0*c/b, x, y);
    if (b == 0)
        return Det(-1.0*c/a, 0, -1.0*c/a, 1, x, y);
    return Det(0, -1.0*c/b, -1.0*c/a, 0, x, y);
}


void Read()
{
    freopen("regiuni.in", "r", stdin);
    scanf("%d %d", &m, &n);
    int a, b, c, x, y, i, j;
    for (i = 1; i<=m; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        d[i] = dreapta(a, b, c);
    }
    for (i = 1; i<=n; ++i)
    {
        scanf("%d %d", &x, &y);
        int hash = 1;
        for (int j=1; j<=m; ++j)
            hash = (hash*X + Side(d[j].a, d[j].b, d[j].c, x, y)) % MOD;
        t[i] = hash;
    }
    sort(t+1, t+n+1);
    int ans = 0;
    for (i = 1; i<=n;)
    {
        ++ans;
        for (j = i; j<=n && t[i] == t[j]; ++j);
        i = j;
    }
    freopen("regiuni.out", "w", stdout);
    printf("%d\n", ans);
}

int main()
{
    Read();
    return 0;
}