Cod sursa(job #38088)

Utilizator cos_minBondane Cosmin cos_min Data 25 martie 2007 14:41:53
Problema Regiuni Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 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;
    int q[4];
    int next, minus;
    int j;
    int aux=0;
    //freopen(in,"r",stdin);
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fscanf(fin,"%d%d", &n, &m);
    fscanf(fin,"\n");
    
    char linie[21];
        
    for ( int i = 1; i <= n; i++ )
    {
        //scanf("%d%d%d", &f, &g, &h);
        fgets(linie,20,fin);
        
        j = 0;
        minus = 1;
        next = 0;
        aux = 0;
        while ( linie[j] != '\n' )
        {
              if ( linie[j] == ' ' )
              {
                   next += 1;
                   q[next] = minus*aux;
                   aux = 0;
                   minus = 1;
              }
              else
              {
                  if ( linie[j] == '-' ) minus = -1;
                  else                   aux *= 10, aux += (int)linie[j]-48;
              }
              j++;
        }
        
        d[i].a = q[1];
        d[i].b = q[2];
        d[i].c = minus*aux;
    }
    
    
    for ( int i = 1; i <= m; i++ ) 
    {
                fgets(linie,20,fin);
        
        j = 0;
        minus = 1;
        next = 0;
        aux = 0;
        while ( linie[j] != '\n' )
        {
              if ( linie[j] == ' ' )
              {
                   next += 1;
                   q[next] = minus*aux;
                   aux = 0;
                   minus = 1;
              }
              else
              {
                  if ( linie[j] == '-' ) minus = -1;
                  else                   aux *= 10, aux += (int)linie[j]-48;
              }
              j++;
        }

        p[i].x = q[1];
        p[i].y = aux*minus;
    }
    
    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;
}