Cod sursa(job #43984)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 30 martie 2007 19:15:59
Problema Regiuni Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#define NMAX 1010
#define VMAX 9001
#define BP1 20664409
#define BP2 23199767
#define BP3 25752941

int N, M, Rep[NMAX], D[NMAX][3];
int A[NMAX][3], Cnt[NMAX], Prime[NMAX], Np, V[VMAX];

int main()
{
        int i, j, x, y, l, c, nreg = 0, sgn;

        for (i = 2; i < VMAX && Np < 1010; i++)
            if (V[i] == 0)
            {
                Prime[Np++] = i;
                for (j = i; j < VMAX; j+=i) V[j] = 1;
            }

        freopen("regiuni.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 1; i <= N; i++) scanf("%d %d %d", D[i]+0, D[i]+1, D[i]+2);

        for (i = 1; i <= M; i++)
        {
                scanf("%d %d", &x, &y);
                l = N/2;
                for (j = 1; j <= N; j++)
                {
                    sgn = 1;
                    if (D[j][0]*x+D[j][1]*y+D[j][2] < 0) sgn = -1;
                    A[i][0] = (A[i][0]+sgn*Prime[j])%BP1;
                    A[i][1] = (A[i][1]+sgn*Prime[N-j])%BP2;
                    A[i][2] = (A[i][2]+sgn*Prime[l%N])%BP3;
                }
        }

        for (i = 1; i <= M; i++) Rep[i] = i;

        for (i = 1; i <= M; i++)
            for (j = i+1; j <= M; j++)
                if (A[i][0]==A[j][0] && A[i][1]==A[j][1] && A[i][2]==A[j][2])
                   Rep[j] = Rep[i];

        for (i = 1; i <= M; i++) Cnt[ Rep[i] ]++;
        for (i = 1; i <= M; i++) nreg += (Cnt[i]>0);

        freopen("regiuni.out", "w", stdout);
        printf("%d\n", nreg);

        return 0;
        
}