Cod sursa(job #276542)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 11 martie 2009 11:07:13
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmax 1024
#define inf 30005
int n,m,a[Nmax][4],i,j,viz[Nmax];
struct asd{int x; int y; int up;int right;};
asd point[Nmax]={0};

int cmp (const void *a,const void *b)
 { return (((asd*)a)->up-((asd*)b)->up); }

int main()
{
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i=1;i<=n;i++)
	scanf("%d%d%d", &a[i][1], &a[i][2], &a[i][3]);
for(i=1;i<=m;i++)
	scanf("%d%d", &point[i].x, &point[i].y);
for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
		{ float s;
		 if(a[j][2]!=0)
			{
			s=(float)(-a[j][1]*point[i].x-a[j][3])/a[j][2];
			if(s>point[i].y)
				point[i].up++;
			else point[i].up--;
			}
		 else { s=(float)(-a[j][3])/a[j][1];
			if(s>point[i].x)
			  point[i].right++;
			else
			  point[i].right--;
			}
		 //x szerint
		 if(a[j][1]!=0)
			{
			 s=(float)(-a[j][2]*point[i].y-a[j][3])/a[j][1];
			if(s>point[i].x)
				point[i].right++;
			else point[i].right--;
			}
		 else { s=(float)(-a[j][3])/a[j][2];
			if(s>point[i].y)
			  point[i].up++;
			else
			  point[i].up--;
			}
		}
 point[0].up=-inf;
 qsort(point,m+1,sizeof(asd),cmp);
 int nr=0;
 for (i=1;i<=m;++i)
  {
   if (!viz[i])
    {
     ++nr;viz[i]=1;
     for (j=i+1;j<=m && point[i].up==point[j].up;++j)
       if (point[i].right==point[j].right) viz[j]=1;
    }
  }
 printf("%d\n",nr);
 return 0;
}