Cod sursa(job #1105069)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 februarie 2014 13:57:11
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;

#define NMAX 1002

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

int n,m,nr;
int f[NMAX];
vector<int>g[NMAX];


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,k,sol=0,ok,nrs;

    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);
        g[1].push_back(i);
    }
    nr=1;

    for(i=1;i<=n;++i)
    {
        nrs=0;
        for(j=1;j<=nr;++j)
        {
            ok=0;
            for(k=g[j].size()-1;k>=0;--k)
                if(dist(d[i],v[g[j][k]]))
                {
                    ok=1;
                    g[nr+1].push_back(g[j][k]);
                    g[j].erase(g[j].begin()+k);
                }
            if(ok)++nrs;
        }
        nr+=nrs;
    }


    for(i=1;i<NMAX;++i)
        if(g[i].size())
            ++sol;

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

    return 0;
}