Cod sursa(job #1815959)

Utilizator silkMarin Dragos silk Data 25 noiembrie 2016 23:03:24
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#define NMax 1000
#include <algorithm>
using namespace std;

const int P = 147481;
const int Q = 4733;

struct point{ int x,y; };
point v[NMax+1];

int a[NMax+1];
int b[NMax+1];
int c[NMax+1];

int f(int i, int x, int y)
{
    return ( a[i]*x + b[i]*y + c[i] > 0 );
}

bool cmp(const point A, const point B)
{
    if( A.x==B.x ) return A.y<B.y;
    return A.x<B.x;
}

int main(){
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);

    int i,j,N,M,x,y,p,q,ans=0;
    int u[3];
    u[0] = 1;
    u[1] = 2;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= N; ++i) scanf("%d %d %d",&a[i],&b[i],&c[i]);
    for(i = 1; i <= M; ++i)
    {
        scanf("%d %d",&x,&y);
        p = q = 0;
        for(j = 1; j <= N; ++j)
        {
            p = ( p*47 + u[ f(j,x,y) ] ) % P;
            q = ( q*47 + u[ f(j,x,y) ] ) % Q;
        }
        v[i].x = p;
        v[i].y = q;
    }

    sort(v+1,v+M+1,cmp);
    for(i = 1; i <= M; )
    {
        for(j = i; j <= M && v[i].x==v[j].x && v[i].y==v[j].y; ++j);
        ++ans;

        i = j;
    }

    printf("%d\n",ans);



return 0;
}