Cod sursa(job #37484)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 25 martie 2007 10:23:44
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.73 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct punct { int x,y; } P[1001];
struct dreapta { int a,b,c; } D[1001];
typedef char sir[1001];         
sir nS[1001],S[1001];
int n,m,nr;

void ReadData ()
{
    int i;
    freopen ( "regiuni.in" , "r" , stdin );
    scanf ( "%d %d" , &m , &n );
    for ( i=0 ; i<m ; i++ ) scanf ( "%d %d %d" , &D[i].a , &D[i].b , &D[i].c );
    for ( i=0 ; i<n ; i++ ) scanf ( "%d %d" , &P[i].x , &P[i].y );
    fclose ( stdin );
}

void WriteData ()
{
    freopen ( "regiuni.out" , "w" , stdout );
    printf ( "%d\n" , nr );
    fclose ( stdout );
}

void MakeStrings ()
{
    int i,j;
    for ( i=0 ; i<n ; i++ )
        for ( j=0 ; j<m ; j++ )
            nS[i][j]='0'+ (D[j].a*P[i].x+D[j].b*P[i].y+D[j].c>0);
}

void MergeStrings ( int l , int mij , int r )
{
    int i,j,k;
    for (i=l, j=mij+1, k=l; i<=mij || j<=r; )
        if (j > r || (i <= mij && (memcmp ( nS[i] , nS[j] , m ) <0 ))) {
            memcpy ( S[k++] , nS[i] , m+1 ); i++; }
        else { memcpy ( S[k++] , nS[j] , m+1 ) ; j++; }
    for ( k=l ; k<=r ; k++ ) memcpy ( nS[k] , S[k] , m+1 );
}

void SortStrings(int l, int r)   
{   
    int m = (l + r) >> 1;   
    if (l == r) return;   
    SortStrings(l, m);   
    SortStrings(m + 1, r);
    MergeStrings ( l , m , r );
}   


void CountGroups ()
{
    sir s[1001];
    int i;
    nr=1; memcpy ( s , S[0] , m+1 );
    for ( i=1 ; i<n ; i++ )
        if ( memcmp ( s , S[i] , m ) ) { memcpy ( s , S[i] , m+1 ); nr++; }
}

void Solve ()
{
    MakeStrings ();
    SortStrings ( 0 , n-1 );
    CountGroups ();
}

int main ()
{
    ReadData ();
    Solve ();
    WriteData ();
    return 0;
}