Cod sursa(job #186495)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 28 aprilie 2008 01:36:55
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define NMAX	1000

struct pct {long  x,y;};
struct segment {long long d;
				pct c;};

void poz(int st,int dr,int &piv,segment x[])
{int i=st,j=dr,d=0;
 segment	t;
 while(i<j) {
			if(x[i].d>x[j].d||x[i].d==x[j].d&&x[i].c.x>x[j].c.x)
					{
					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,segment x[])
{int piv;
 if(left<right) {poz(left,right,piv,x);
				 qsrt(left,piv-1,x);
				 qsrt(piv+1,right,x);
				}
}
/*
int cauta(int ls,int ld,rpt x[],long val)
{
int i=ls,j=ld,mij;
while(ls<=ld){
	mij=(ls+ld)/2;
	if(val==x[mij].dy) return mij;
	else if(val>x[mij].dy) ls=mij+1;
		 else ld=mij-1;
	}
return -1;
}
  */
int main()
{
//clrscr();
freopen("patrate3.in","r",stdin);
freopen("patrate3.out","w",stdout);
int n,i,j,k,nrptr;
long dx,dy;

pct	v[NMAX]={{0L,0L}};
segment r[NMAX*(NMAX-1)/2]={{0.0,{0,0}}};
scanf("%d",&n);
i=0;
long double x,y;
while(i<n) {
	scanf("%Lf%Lf", &x,&y);
	(v+i)->x=ceill(x*10000.0);
	(v+i)->y=ceill(y*10000.0);
	i++;
	}

//construiesc segmente d si c
k=0;
for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		{
		dx=v[i].x-v[j].x; x=dx;
		dy=v[i].y-v[j].y; y=dy;
		//r[k].d=sqrt(x*x+y*y);
		r[k].d=dx*dx+dy*dy;
		r[k].c.x=(v[i].x+v[j].x)/2;
		r[k].c.y=(v[i].y+v[j].y)/2;
		k++;
		}
/*
for(i=0;i<k;i++) printf("(%11.2ld %11ld %11ld)\n",
				 r[i].d,r[i].c.x,r[i].c.y);
printf("\n");*/

//sortez segmentele
qsrt(0,k-1,r);
/*
for(i=0;i<k;i++) printf("(%11lld %11ld %11ld)\n",
				 r[i].d,r[i].c.x,r[i].c.y);
printf("\n");  */

nrptr=0;
for(i=0;i<k-3;i++){
	if((r[i].d==r[i+1].d)&&(r[i].c.x==r[i+1].c.x&&r[i].c.y==r[i+1].c.y))
		{nrptr++;
	   /*	printf("(%11lld %11ld %11ld)\n",
				 r[i].d,r[i].c.x,r[i].c.y);*/
		i=i+1;
		}
	}
printf("%d",nrptr);
return 0;
}