Cod sursa(job #46116)

Utilizator pustiuRadu Zaharia pustiu Data 2 aprilie 2007 12:48:58
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#include<math.h>
#define Nmax 1000
#define Mmax 1000

FILE *in = fopen ("regiuni.in" , "rt");
FILE *out = fopen ("regiuni.out" , "wt");

struct dreapta {int a,b,c;};

int A[Nmax][Mmax];
dreapta X[Mmax];
long long lista[Nmax];

int N,M;

void citire_M ()
{
	fscanf (in , "%d %d", &M,&N);
    for (int i=1;i<=M;i++)
    {
    	fscanf (in, "%d %d %d", &X[i].a, &X[i].b, &X[i].c);
    }
}

void citire_N ()
{
	for(int i=1;i<=N;i++)
    {
    	A[i][0]=i;
    	int x,y;
    	fscanf (in, "%d %d", &x, &y);
        for (int j=1;j<=M;j++)
        {
        	int r;
            r=X[j].a*x+X[j].b*y+X[i].c;
            if(r>0)
            	A[i][j]=1;
        }
    }
}

void calc ()
{
	for(int i=1;i<=N;i++)
    	for(int j=1;j<=M;j++)
        {
        	if(A[i][j])
            {
            	lista[i]+=pow(2,M-j);
            }
        }
}

void schimba (int &x, int &y)
{
	int aux=x; x=y; y=aux;
}

void schimba (long long &x, long long &y)
{
	int aux=x; x=y; y=aux;
}

void delimiteaza (int s, int d, int &m)
{
	int i=s,j=d, pi=0, pj=1;
    while(i<j)
    {
    	if(lista[i]>lista[j])
        {
        	schimba (lista[i],lista[j]);
            schimba (pi,pj);
        }
    i+=pi;
    j-=pj;
    }
    m=i;
}

void qsort (int s, int d)
{
	int m;
    if(s<d)
	{
    	delimiteaza (s,d,m);
        qsort(s,m-1);
        qsort(m+1,d);
    }
}

int regiuni ()
{
    int reg=0;
    for(int i=1;i<=N-1;i++)
    	if(lista[i]!=lista[i+1])
        	reg++;
	return reg;
}

int main (void)
{
	citire_M();
    citire_N();
    calc();
    qsort(1,N);
    int x=regiuni()+1;
    fprintf(out, "%d\n", x);
    fclose(in);
    fclose(out);
}