Cod sursa(job #303626)

Utilizator Mishu91Andrei Misarca Mishu91 Data 10 aprilie 2009 01:48:58
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>

#define MAX_N 1005
#define INF 1000000.0

struct point
{
    double x, y;
};

struct line
{
    int a, b, c;
} A[MAX_N];

typedef struct nod
{
    int x, y;
    nod *next;
} *list;

list H[MAX_N];

int N, M, K = 1;

void add(list &L, int x, int y)
{
    list t = new nod;
    t -> x = x;
    t -> y = y;
    t -> next = L;
    L = t;
}

void citire()
{
    scanf("%d %d",&N, &M);

    for(int i = 1; i <= N; ++i)
        scanf("%d %d %d", &A[i].a, &A[i].b, &A[i].c);

    for(int i = 1; i <= M; ++i)
    {
        int x, y;
        scanf("%d %d",&x, &y);

        add(H[1], x, y);
    }

}

int sign(point p0, point p1, point p2)
{
    double t = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);

    if(t >= 0) return 1;
    return -1;
}

int a, b, c;

void solve()
{
    for(int i = 1; i <= N; ++i)
    {
        a = A[i].a;
        b = A[i].b;
        c = A[i].c;

        point p0, p1, p2;

        if(b == 0)
            p1.x = -(double)c / a,
            p1.y = 0.0;
        else
            p1.x = 0.0,
            p1.y = -(double)c / b;

        if(b == 0)
            p2.x = -(double)c / a,
            p2.y = 1.0;
        else
            p2.x = 1.0,
            p2.y = -(double)(c + a) / b;

        int k = K;
        for(int j = 1; j <= k; ++j)
        {
            if(H[j] == NULL) continue;
            
            p0.x = H[j] -> x;
            p0.y = H[j] -> y;
            bool ok = 0;

            int s = sign(p0, p1, p2);

            for(list p = H[j]; p -> next;)
            {
                p0.x = p -> next -> x;
                p0.y = p -> next -> y;

                if(sign(p0, p1, p2) != s)
                {
                    list aux = p -> next;
                    p -> next = aux -> next;

                    if(!ok) ++K, ok = 1;

                    add(H[K], aux -> x, aux -> y);
                    delete aux;
                }
                else
                    p = p -> next;
            }
        }

        #ifdef _HOME_
        for(int i = 1; i <= 3; ++i)
        {
            for(list p = H[i]; p; p = p -> next)
                fprintf(stderr, "%d %d   ", p -> x, p -> y);
           fprintf(stderr, "\n");
        }
        #endif
    }

    int Sol = 0;
    for(int i = 1; i <= M; ++i)
        if(H[i]) ++Sol;

    printf("%d\n",Sol);
}

int main()
{
    freopen("regiuni.in","rt",stdin);
    freopen("regiuni.out","wt",stdout);

    citire();
    solve();
}