Cod sursa(job #40579)

Utilizator alecmanAchim Ioan Alexandru alecman Data 27 martie 2007 15:31:55
Problema Regiuni Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 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[1001][3],panta[1001],total;
long suma[1001];
char contor[1001];

void citire();
//void init();
void rezolvare(int x, int y);
int sortat(const void *a, const void *b);
void calcul();
void quick(int st, int dr);

int main()
{
  citire();
//  init();
  total=0;
  int x,y;
  for(int i=1;i<=m;++i)
  {
    fscanf(fin, "%d %d", &x,&y);
    rezolvare(x,y);
  }
//  qsort((void*)contor,m,sizeof(contor[0]),sortat);
  quick(0,m-1);
  calcul();
/*  for(int i=0;i<m;++i)
     delete [] contor[i];*/
  fclose(fin);
  fclose(fout);
  return 0;
}

void citire()
{
  fscanf(fin, "%d %d", &n, &m);
  for(int i=1;i<=n;++i)
  {
    fscanf(fin, "%d %d %d", &dr[i][0],&dr[i][1],&dr[i][2]);
    if(dr[i][0]==0)
      panta[i]=1;
    else
    if(dr[i][1]==0)
      panta[i]=2;
    else
      panta[i]=3;
  }
}
/*
void init()
{
  for(int i=0;i<m;++i)
  {
    contor[i]=new char[m];
    memset(contor[i],0,sizeof(contor[i]));
  }
}*/

void rezolvare(int x, int y)
{
  ++total;
  double valverif;
    for(int j=1;j<=n;++j)
    {
      if(panta[j]==1)
      {
        valverif=(double)(-dr[j][2]/dr[j][1]);
        if(y>valverif)
          contor[j-1]='2';
        else
          contor[j-1]='1';
      }
      else
      if(panta[j]==2)
      {
        valverif=(double)(-dr[j][2]/dr[j][0]);
        if(x>valverif)
          contor[j-1]='2';
        else
          contor[j-1]='1';
      }
      else
      {
        valverif=(double)((-dr[j][2]-dr[j][0]*x));
        valverif=valverif/dr[j][1];
        if(valverif<y)
          contor[j-1]='2';
        else
          contor[j-1]='1';
      }
    }
  suma[total-1]=0;
  for(int i=0;i<n;++i)
  {
    if(contor[i]=='1')
       suma[total-1]+=(i+1)*5;
    else
       suma[total-1]+=(i+1)*10;
  }
}
/*
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(suma[i]!=suma[i-1])
     ++numar;
  }
  fprintf(fout, "%d\n", numar);
}

void quick(int st, int dr)
{
  int l=st,m=dr;
  while(l!=m)
  {
    if((l<m&&suma[l]>suma[m])||(l>m&&suma[l]<suma[m]))
    {
      suma[l]=suma[l]+suma[m];
      suma[m]=suma[l]-suma[m];
      suma[l]=suma[l]-suma[m];
      l=l+m;
      m=l-m;
      l=l-m;
      if(l<m)
        --m;
      else
        ++m;
    }
    else
      if(l<m)
        --m;
      else
        ++m;
  }
  if(l!=st) quick(st,l-1);
  if(l!=dr) quick(l+1,dr);
}