Cod sursa(job #39913)

Utilizator alecmanAchim Ioan Alexandru alecman Data 27 martie 2007 09:06:03
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
/*
 *
 *
  info-arena 2.0 - preONI 2007 Finala - Regiuni
 *
 *
 */

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define INPUT "regiuni.in"
#define OUTPUT "regiuni.out"

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

int n,m,*dr[3],*pct[2],*panta;
char *contor[1001];

void init();
void citire();
void rezolvare();
int sortat(const void *a, const void *b);
void calcul();

int main()
{
  init();
  citire();
  rezolvare();
  qsort((void*)contor,m,sizeof(contor[0]),sortat);
  calcul();
  delete [] panta;
  fclose(fin);
  fclose(fout);
  return 0;
}

void init()
{
  for(int i=0;i<=1000;++i)
  {
    contor[i]=new char[1001];
    memset(contor[i],0,sizeof(contor[i]));
  }
  dr[0]=new int[1001];
  dr[1]=new int[1001];
  dr[2]=new int[1001];
  pct[0]=new int[1001];
  pct[1]=new int[1001];
  panta=new int[1001];
}

void citire()
{
  fscanf(fin, "%d %d", &n, &m);
  for(int i=1;i<=n;++i)
  {
    fscanf(fin, "%d %d %d", &dr[0][i],&dr[1][i],&dr[2][i]);
    if(dr[0][i]==0)
      panta[i]=1;
    else
    if(dr[1][i]==0)
      panta[i]=2;
    else
      panta[i]=3;
  }
  for(int i=1;i<=m;++i)
    fscanf(fin, "%d %d", &pct[0][i],&pct[1][i]);
}

void rezolvare()
{
  double valverif;
  for(int i=1;i<=m;++i)
  {
    for(int j=1;j<=n;++j)
    {
      if(panta[j]==1)
      {
        valverif=(double)(-dr[2][j]/dr[1][j]);
        if(pct[1][i]>valverif)
          contor[i-1][j-1]='2';
        else
          contor[i-1][j-1]='1';
      }
      else
      if(panta[j]==2)
      {
        valverif=(double)(-dr[2][j]/dr[0][j]);
        if(pct[0][i]>valverif)
          contor[i-1][j-1]='2';
        else
          contor[i-1][j-1]='1';
      }
      else
      {
        valverif=(double)((-dr[2][j]-dr[0][j]*pct[0][i]));
        valverif=valverif/dr[1][j];
        if(valverif<pct[1][i])
          contor[i-1][j-1]='2';
        else
          contor[i-1][j-1]='1';
      }
    }
  }
}

int sortat(const void *a, const void *b)
{
  return (strcmp((char*)a,(char*)b));
}

void calcul()
{
  int numar=1;
  for(int i=1;i<m;++i)
  {
    if(strcmp(contor[i],contor[i-1])!=0)
     ++numar;
  }
  fprintf(fout, "%d\n", numar);
}