Cod sursa(job #384683)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 20 ianuarie 2010 18:21:49
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<vector>
#define MOD 19999
using namespace std;
struct regiune
{
    int a,b,c;
};
struct punct
{
    int x,y;
};
regiune v[1005],x[1005];
int n,m;
int reg,key;
vector <punct> hash[MOD];
int calcul (int linia,int px,int py)
{
    int E = v[linia].a*px + v[linia].b*py + v[linia].c;
    if (E > 0) return +1;
    if (E < 0) return -1;
    return 0;
}
int cheie (int put)
{
    if(!put)
        return 1;
    int p=cheie(put/2);
    if(!(put%2))
        return ((p*p)%MOD);
    return ((((p*p)%MOD)*2)%MOD);
}
int find (int key,int px,int py)
{
    int i,nr=hash[key].size();
    int r1,r2,val,j;
    for(i=0;i<nr;i++)
    {
        val=0;
        for(j=1;j<=n;j++)
        {
            r1=calcul(j,px,py);
            r2=calcul(j,hash[key][i].x,hash[key][i].y);
            if(r1!=r2)
                break;
        }
        if(j==n+1)
            return 1;
    }
    return 0;
}

void insert (int key,punct pct)
{
    hash[key].push_back(pct);
}

int main ()
{
    int i,j,r,xa,xb,val;
    punct pct;
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);

    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&xa,&xb);
        val=0;
        for(j=1;j<=n;j++)
        {
            r=calcul(j,xa,xb);
            if(r>0)
            {
                val+=cheie(j-1);
                val%=MOD;
            }
        }
        if(!find(val,xa,xb))
        {
            pct.x=xa;pct.y=xb;
            insert(val,pct);
            reg++;
        }
    }
    printf("%d\n",reg);
    return 0;
}