Cod sursa(job #189464)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 14 mai 2008 17:15:49
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<stdio.h>
#include<math.h>

#define NMAX 1500
#define DIF	 0.0001

struct pct{ double x,y;};
pct v[NMAX];

void poz(int stg,int dr,int &piv){
int i=stg,j=dr,d=0;
pct aux;
while(i<j){
	if(v[i].x>v[j].x||
	fabs(v[i].x-v[j].x)<0.0001&&v[i].y>v[j].y){
		aux=v[i];v[i]=v[j];v[j]=aux;d=1-d;
		}
	i+=d;
	j-=1-d;
	}
piv=i;
}

void qsort(int li,int ls){
int piv;
if(li<ls){
	poz(li,ls,piv);
	qsort(li,piv-1);
	qsort(piv+1,ls);
	}
}

int main(){
freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
int i,j,k,n,nrtr=0,up;
double x,y,d1,d1p,dx,dy,r3=sqrt(3),
	   dx2,dy2,dxop,dyop,d2p,d2,
	   eps,dx3,dy3,d3p,d3,eps2,xmin,ymin;
scanf("%d",&n);
for(i=0;i<n;i++) {scanf("%lf%lf",&x,&y);v[i].x=x;v[i].y=y;}
qsort(0,n-1);
for(i=0;i<n-2;i++){
	for(j=i+1;j<n-1;j++){
		dx=v[j].x-v[i].x;
		if(v[j].y>=v[i].y) {up=1;dy=v[j].y-v[i].y;}
		else {up=0;dy=v[i].y-v[j].y;}
		if(dy<dx/r3-DIF) continue;
		d1p=dx*dx+dy*dy; d1=sqrt(d1p);
		dxop=dx/2+dy*r3/2;
		if(up) dyop=dy/2-dx*r3/2;
		else dyop=dx*r3/2-dy/2;
		//dyop=dy/2-dx*r3/2;
		//if(dyop<0) dyop=-dyop;
		xmin=v[i].x+dxop;
		//if(up) ymin=v[i].y-dyop;
		//else ymin=v[i].y+dyop;
		ymin=v[i].y+dyop;
		for(k=j+1;k<n&&v[k].x<xmin+DIF;k++){
			if(v[k].x<xmin-DIF) continue;
		   	if(v[k].y<ymin-DIF||v[k].y>ymin+DIF) continue;
			dx2=v[k].x-v[i].x;
			if(v[k].y>v[i].y) dy2=v[k].y-v[i].y;
			else dy2=v[i].y-v[k].y;
			if(dy2>dx2/r3+DIF) continue;

			//up2=1 k deasupra lui j
			d2p=dx2*dx2+dy2*dy2;d2=sqrt(d2p);
			dx3=v[k].x-v[j].x;
			if(v[k].y>v[j].y) dy3=v[k].y-v[j].y;
			else dy3=v[j].y-v[k].y;
			d3p=dx3*dx3+dy3*dy3;d3=sqrt(d3p);
		   /*	if(!up2&&dy2>dyop+DIF) continue;
			if(up2&&dy2>dyop+DIF) break; */
			eps=d1-d2;if(eps<0) eps=-eps;
			eps2=d1-d3;if(eps2<0) eps2=-eps2;
			if(eps<=DIF&&eps2<=DIF) nrtr++;
		 /*	printf("%0.4lf %0.4lf ",v[i].x,v[i].y);
			printf("%0.4lf %0.4lf ",v[j].x,v[j].y);
			printf("%0.4lf %0.4lf\n",v[k].x,v[k].y);}*/
			}
		}
	}
printf("%d",nrtr);
return 0;
}