Cod sursa(job #1073426)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 6 ianuarie 2014 10:59:09
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#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];
struct punct
{
    int x, y;
    punct() {}
    punct(const int _x, const int _y)
    {
        x = _x, y = _y;
    }
};
punct p[NMax];

int n, m;
int side[MMax][NMax];
int t[NMax];
// a[i][j] = de care parte a dreptei i se afla punctul j

void Read()
{
    ifstream f ("regiuni.in");
    f>>m>>n;
    for (int i = 1; i<=m; ++i)
    {
        int a, b, c;
        f>>a>>b>>c;
        d[i] = dreapta(a, b, c);
    }
    for (int i = 1; i<=n; ++i)
    {
        int x, y;
        f>>x>>y;
        p[i] = punct(x, y);
    }
    f.close();
}

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 Solve()
{
    int i, j;
    for (i = 1; i<=m; ++i)
        for (j=1; j<=n; ++j)
            side[i][j] = Side(d[i].a, d[i].b, d[i].c, p[j].x, p[j].y);

    for (i=1; i<=n; ++i)
    {
        int hash = 1;
        for (j=1; j<=m; ++j)
            hash = (hash*X + side[j][i]) % MOD;
        t[i] = hash;
    }
    sort(t+1, t+n+1);
    int ans = 0;
    t[0] = -1;
    for (i = 1; i<=n;)
    {
        ++ans;
        for (j = i; j<=n && t[i] == t[j]; ++j);
        i = j;
    }
    ofstream g("regiuni.out");
    g<<ans<<"\n";
    g.close();

}

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