Cod sursa(job #36537)

Utilizator t30Rosu Teodor t30 Data 23 martie 2007 18:05:36
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define M 0.001
typedef struct punct { double x,y; } punct;
punct x[1600];
int n;
long nr;
double xx1,xx2,yy1,yy2;


int cmp(const void *x,const void *y){
   punct *xx=(punct *)x,*yy=(punct *)y;
   if(xx->x - yy->x > M ) return 1;
   if(xx->x - yy->x < -M ) return -1;
   if(xx->y - yy->y > M) return 1;
   if(xx->y - yy->y <-M ) return -1;
   return 0;
}

void READ(){
FILE *f;
int i;
	f=fopen("triang.in","r");
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
	   fscanf(f,"%lf %lf",&x[i].x,&x[i].y);
	fclose(f);
}

void calcul(double xa,double ya,double xb,double yb){
double a,b,A,B;
	b=yb-ya;
	a=xb-xa;

	B=(xb*xb-xa*xa+yb*yb-ya*ya)/2;
	A=xa*yb-xb*ya+((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb) ) /2*sqrt(3);

	xx1=(A*b+B*a)/(a*a+b*b);
	yy1=(-A*a+B*b)/(a*a+b*b);

	A=xa*yb-xb*ya-((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))/2*sqrt(3);

	xx2=(A*b+B*a)/(a*a+b*b);
	yy2=(-A*a+B*b)/(a*a+b*b);
}

int caut(long xx, long yy){
int p,i;
	for(p=1;p<=n;p<<=1);
	for(i=0;p;p>>=1){
	   if(i+p<=n && ( xx>=(long)(x[i+p].x*1000) || (xx==(long)(x[i+p].x*1000) && yy>=(long)(x[i+p].y*1000)) ))
	      i+=p;
	}


if( xx-(long)(x[i].x*1000)>=-1 && xx-(long)(x[i].x*1000)<=1 && yy-(long)(x[i].y*1000)<=1 && yy-(long)(x[i].y*1000)>=-1 ) return 1;
return 0;

}


void SOLVE(){
int i,j,ok,ii,jj;
long xx,yy;
   for(i=1;i<n;i++)
     for(j=i+1;j<=n;j++){
	calcul(x[i].x,x[i].y,x[j].x,x[j].y);
	xx=1000*xx1;
	yy=1000*yy1;
	ok=0;
	for(ii=0;!ok && ii<=1;ii++){
	   for(jj=0;!ok && jj<=1;jj++)
	      ok=caut(xx+ii,yy+jj);
	}
	nr+=ok;
	xx=1000*xx2;
	yy=1000*yy2;
	ok=0;
	for(ii=0;!ok && ii<=1;ii++){
	   for(jj=0;!ok && jj<=1;jj++)
	      ok=caut(xx+ii,yy+jj);
	}
	nr+=ok;
     }
}

void PRINT(){
   FILE *g;
   g=fopen("triang.out","w");
   fprintf(g,"%ld",nr/3);
   fclose(g);
}

int main(){
	READ();
	qsort(x+1,n,sizeof(punct),cmp);
	SOLVE();
	PRINT();

return 0;
}