Cod sursa(job #187035)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 29 aprilie 2008 23:44:40
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
#define NMAX	1000
#define DIF 0.00001
struct pct {double  x,y;};

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

void qsrt(int left,int right,pct x[])
{int piv;
 if(left<right) {poz(left,right,piv,x);
				 qsrt(left,piv-1,x);
				 qsrt(piv+1,right,x);
				}
}

int main()
{
freopen("patrate3.in","r",stdin);
freopen("patrate3.out","w",stdout);
int n,i,j,k,l,nrptr;
pct	v[NMAX]={{0.0,0.0}};
scanf("%d",&n);
i=0;
double x,y;
while(i<n) {
	scanf("%lf%lf", &x,&y);
	(v+i)->x=x;
	(v+i)->y=y;
	i++;
	}
qsrt(0,n-1,v);

for(i=0;i<n;i++)
	printf("%lf %lf\n",v[i].x,v[i].y);
double dx,dy,dij,dik,dil,djl,dmare;
int diag,ok,latura;
double xmax,xmin;
nrptr=0;
for(i=0;i<n-3;i++)
	for(j=i+1;j<n-2;j++)
		{
		dx=v[j].x-v[i].x;
		if(v[j].y<v[i].y) dy=v[i].y-v[j].y;
		else dy=v[j].y-v[i].y;
		if(dy<dx-DIF) continue;

		dij=sqrt(dx*dx+dy*dy);
		dmare=dij*sqrt(2);
		xmax=v[j].x+dy; xmin=v[i].x+dy;
		for(k=j+1;k<n-1&&v[k].x<=xmax+DIF;k++)
			{
		 //	if(v[k].x<(xmin-DIF)||v[k].x>(xmin+DIF)&&v[k].x<(xmax-DIF)) continue;
			dx=v[k].x-v[i].x;
			if(v[k].y<v[i].y) dy=v[i].y-v[k].y;
			else dy=v[k].y-v[i].y;
		  //	if(dy>dx+DIF) continue;

		 //	dy=v[i].y-v[k].y;
			dik=sqrt(dx*dx+dy*dy);
			diag=0;latura=0;ok=0;
			if(fabs(dik-dij)<DIF) {latura=1;ok=1;}
		   //	if(!ok) if(fabs(dik-dmica)<DIF) {diag=1;ok=1;}
			if(!ok) if(fabs(dik-dmare)<DIF) {diag=2;ok=1;}
			if(ok)
				for(l=k+1;l<n&&v[l].x<=xmax+DIF;l++)
					{
					dx=v[i].x-v[l].x;
					dy=v[i].y-v[l].y;
					dil=sqrt(dx*dx+dy*dy);
					dx=v[j].x-v[l].x;
					dy=v[j].y-v[l].y;
					djl=sqrt(dx*dx+dy*dy);
					if(latura&&fabs(dmare-dil)<DIF&&fabs(dij-djl)<DIF)
						{nrptr++;
  //	printf("latura %lf %lf %lf %lf\n",dij,dik,dil,djl);
	}
					if(diag==2)
						if(fabs(dij-dil)<DIF&&fabs(dmare-djl)<DIF)
						{nrptr++;
  //	printf("dmare %lf %lf %lf %lf\n",dij,dik,dil,djl);
	}
					}
			}
		}
printf("%d",nrptr);
return 0;
}