Cod sursa(job #189254)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 13 mai 2008 02:19:42
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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||v[i].x==v[j].x&&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,up2;
double x,y,d1,d1p,dx,dy,r3=sqrt(3),
	   dx2,dy2,dxop,dyop;

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(!up&&dy>dx/r3+DIF) continue;
		if(up&&dy<dx/r3-DIF) continue;
		d1p=dx*dx+dy*dy; d1=sqrt(d1p);
		for(k=j+1;k<n;k++){
			dx2=v[k].x-v[i].x;
			dxop=dx/2+dy*r3/2;
			if(dx2<dxop-DIF) continue;
			if(dx2>dxop+DIF) break;
			dyop=dy/2+dx*r3/2;
			if(v[k].y>=v[j].y) {up2=1;dy2=v[k].y-v[j].y;}
			else {up2=0;dy2=v[j].y-v[k].y;}
			if(up&&!up2&&dy2>dyop+DIF) continue;
			if(!up&&up2&&dy2<dyop-DIF) break;
			else nrtr++;
			}
		}
	}
printf("%d",nrtr);
return 0;
}