Cod sursa(job #285355)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 22 martie 2009 15:31:55
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#include <vector>
#include <set>

#define maxn 1010
#define pb push_back

using namespace std;

long n, m, i, j, k, s, l[maxn], e[maxn], ok;
long x[maxn], y[maxn], a[maxn], b[maxn], c[maxn];
vector< set<long> > v;
set <long> cur;

long semn(long i, long j)
{
    long ec=a[i]*x[j]+b[i]*y[j]+c[i];
    if(ec>0) return 1;
    return -1;
}

int main()
{
    set<long> :: iterator it;
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);
    scanf("%d %d\n", &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[i], &y[i]);
        cur.insert(i);
    }
    v.pb(cur);
    for(i=1; i<=n; i++)
    {
        for(j=0; j<v.size(); j++)
        {
            cur.clear();
            for(k=1, it=v[j].begin(); it!=v[j].end(); it++, k++)
            {
                e[k]=*it;
                l[k]=semn(i, *it);
            }
            s=k-1;
            ok=0;
            for(k=1; k<=s; k++)
            {
                if(l[k]!=l[1])
                {
                    cur.insert(e[k]);
                    v[j].erase(e[k]);
                }
            }
            if(!cur.empty())
            {
                v.pb(cur);
            }
        }
    }
    printf("%d\n", v.size());
    return 0;
}