Cod sursa(job #37631)

Utilizator robbyRobertino robert robby Data 25 martie 2007 11:32:14
Problema Regiuni Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 0.9 kb
#include <stdio.h>
typedef struct punct{int x,y;};
typedef struct dreapta{int a,b,c;};
punct p[1001];
dreapta d[1001];
int reg[1001];
FILE *f,*g;
int main()
{
  int n,m,i,j,r,k,ok,ok2;
  long long xx,yy;
  f=fopen("regiuni.in","rt");
  g=fopen("regiuni.out","wt");
  fscanf(f,"%d %d\n",&n,&m);
  for (i=1;i<=n;i++)
	fscanf(f,"%d %d %d\n",&d[i].a,&d[i].b,&d[i].c);
  for (i=1;i<=m;i++)
	fscanf(f,"%d %d\n",&p[i].x,&p[i].y);
  r=1;
  reg[1]=1;
  for (i=1;i<=m;i++)
	{
	if (!reg[i])
	  reg[i]=++r;
	for (j=i+1;j<=m;j++)
	  {
		ok2=1;
		for (k=1;k<=n;k++)
		  {
		   xx=(long long)p[i].x*d[k].a+(long long)p[i].y*d[k].b+(long long)d[k].c;
		   yy=(long long)p[j].x*d[k].a+(long long)p[j].y*d[k].b+(long long)d[k].c;
		   if ((xx)*(yy)<0)
			{
			  ok2=0;
			  break;
			}
		  }
		if (ok2)
		  reg[j]=reg[i];
	  }
	}
  fprintf(g,"%d\n",r);
  fclose(f);
  fclose(g);
  return 0;
}