Cod sursa(job #1105509)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 februarie 2014 20:49:21
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

#define NMAX 1002
#define MIN 30000

struct punct
{
    int x,y;
}v[NMAX];
struct dreapta
{
    int a,b,c;
}d[NMAX];
struct grupa
{
    int g,n;
}f[NMAX];

int vit[NMAX];
int n,m,nr;


inline bool cmp(const grupa &a,const grupa &b)
{
    return a.g<b.g;
}

inline bool dist(const dreapta &d,const punct &p)
{
    return (((d.a*p.x)+(d.b*p.y)+d.c)/sqrt(d.a*d.a+d.b*d.b))  >0;
}

int main()
{
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);
    int i,j,sol=0,nou;

    nr=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        //v[i].x+=MIN;
        //v[i].y+=MIN;

        f[i].g=vit[i]=nr;
        f[i].n=i;
    }

    for(i=1;i<=n;++i)
    {
        sort(f+1,f+1+n,cmp);
        for(j=1;j<=m;++j)
            vit[j]=f[j].g;
        nou=0;
        for(j=1;j<=m;++j)
        {
            if(f[j].g!=f[j-1].g)nou=1;
            if(dist(d[i],v[f[j].n]))
            {
                if(nou==1)
                {
                    nou=0;
                    ++nr;
                }
                vit[j]=nr;
            }
        }
        for(j=1;j<=m;++j)
            f[j].g=vit[j];
    }


    sort(f,f+1+n,cmp);
    for(i=1;i<=m;++i)
        if(f[i].g!=f[i-1].g)
            ++sol;

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

    return 0;
}