Cod sursa(job #37701)

Utilizator cos_minBondane Cosmin cos_min Data 25 martie 2007 12:04:41
Problema Regiuni Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.55 kb
#include <stdio.h>
#include <set>
using namespace std;

#define in "regiuni.in"
#define out "regiuni.out"
#define dim 1001

int n, m;
struct punct { int x, y; } p[dim];
struct dreapta { int a, b, c; } d[dim];
int sel[dim];

set<int> total;

int Ok(punct A, punct B);

int main()
{
    int f,g,h;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &n, &m);
    
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%d%d%d", &f, &g, &h);
        d[i].a = f;
        d[i].b = g;
        d[i].c = h;
    }
    
    for ( int i = 1; i <= m; i++ ) 
    {
        scanf("%d%d", &f, &g);
        p[i].x = f;
        p[i].y = g;
    }
    
    for ( int i = 1; i < m; i++ )
    {
        if ( sel[i] > 0 ) continue;
        for ( int j = i+1; j <= m; j++ )
        {
            if ( Ok(p[i],p[j]) ) sel[j] = i, sel[i] = i;
        }
        if ( !sel[i] ) sel[i] = i;
    }
    
    if ( !sel[m] ) sel[m] = m;
    
    for ( int i = 1; i <= m; i++ )
    {
       // printf("%d ", sel[i]);
        int k = sel[i];
        total.insert(k);
    }
    
    printf("%d",total.size());
}

int Ok(punct A, punct B)
{
    int v1, v2;
    for ( int i = 1; i <= n; i++ )
    {
        if ( d[i].a*A.x + d[i].b*A.y + d[i].c <= 0 ) v1 = -1;
        else                                         v1 = 1;
        
        if ( d[i].a*B.x + d[i].b*B.y + d[i].c <= 0 ) v2 = -1;
        else                                         v2 = 1;
        
        if ( v1 != v2 ) return 0;
    }
    return 1;
}