Cod sursa(job #48533)

Utilizator CommanderKUPB - Andrei Homescu CommanderK Data 4 aprilie 2007 21:24:38
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

#define	REP( i, n )         for( (i) = 0 ; (i) < (n) ; (i)++ )
#define	IREP( i, n )	    for( (i) = (n) - 1 ; (i) >= 0 ; (i)-- )
#define REPV( i, a, b )     for( (i) = (a) ; (i) <= (b) ; (i)++ )
#define IREPV( i, a, b )    for( (i) = (b) ; (i) >= (a) ; (i)-- )
#define REPIT( it, x )      for( (it) = (x).begin( ) ; (it) != (x).end( ) ; (it)++ )
#define ALL( x )            (x).begin( ), (x).end( )
#define MP                  make_pair
#define PB                  push_back
#define CLR( x )            memset( (x), 0, sizeof( x ) )
#define CLRV( x, v )        memset( (x), (v), sizeof( x ) )
#define CPY( y, x )         memcpy( (y), (x), sizeof( x ) )
#define	X                   first
#define Y                   second

typedef long long Ll;
typedef pair< int, int > Pii;
typedef pair< Ll, Ll > Pll;
typedef vector< int > Vi;
typedef vector< Ll > Vl;
typedef vector< string > Vs;
typedef vector< Vi > Vvi;

const int MAXN = 1024, INF = 0x3f3f3f3f;
const Ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

struct Dreapta
{
    int a, b, c;
} dr[MAXN];

int m, n;
Pii pct[MAXN];
Vvi grupuri;
    
int main( )
{
    freopen( "regiuni.in", "r", stdin );
    freopen( "regiuni.out", "w", stdout );
    
    int i, j, k;
    scanf( "%d%d", &n, &m );
    for( i = 0 ; i < n ; i++ )
        scanf( "%d%d%d", &dr[i].a, &dr[i].b, &dr[i].c );
    for( i = 0 ; i < m ; i++ )
        scanf( "%d%d", &pct[i].X, &pct[i].Y );
        
    Vi v1( m ), v2;
    for( i = 0 ; i < m ; i++ )
        v1[i] = i;
    grupuri.PB( v1 );
    
    for( i = 0 ; i < n ; i++ )
    {
        int ngr = grupuri.size( );
        for( j = 0 ; j < ngr ; j++ )
        {
            Vi &cgr = grupuri[j];
            int n1 = 0, ncgr = cgr.size( );
            for( k = 0 ; k < ncgr ; k++ )
                if(  dr[i].a * pct[cgr[k]].X 
                     + dr[i].b * pct[cgr[k]].Y + dr[i].c < 0 )
                    n1++;
                    
            if( n1 > 0 && n1 < ncgr )
            {
                v1.clear( );
                v2.clear( );            
                for( k = 0 ; k < ncgr ; k++ )
                    if(  dr[i].a * pct[cgr[k]].X 
                         + dr[i].b * pct[cgr[k]].Y + dr[i].c < 0 )
                        v1.PB( cgr[k] );
                    else
                        v2.PB( cgr[k] );    
                        
                cgr = v1;
                grupuri.PB( v2 );
            }
        } 
    }  
    
    printf( "%d", grupuri.size( ) );
    return 0;    
}