Pagini recente » Cod sursa (job #2843451) | Cod sursa (job #2081594) | Cod sursa (job #1889842) | Cod sursa (job #2421393) | Cod sursa (job #40574)
Cod sursa(job #40574)
/*
*
*
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,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);
else
suma[total-1]+=(i+1)*2;
}
}
/*
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);
}