Cod sursa(job #186514)

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

struct pct {long  x,y;};
struct segment {
	long d;
	float p;
	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;
float dxx,dyy;
pct	v[NMAX]={{0L,0L}};
segment r[NMAX*(NMAX-1)/2]={{0L,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; dxx=dx;
		dy=v[i].y-v[j].y; dyy=dy;
		r[k].d=sqrt(dxx*dxx+dyy*dyy);
		//r[k].d=sqrt(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;
		if(fabs(dyy)>0.00001) r[k].p=dxx/dyy;
		else  r[k].p=LONG_MAX;
		k++;
		}
/*
for(i=0;i<k;i++) printf("(%11ld %11.4lf %11ld %11ld)\n",
				 r[i].d,r[i].p, r[i].c.x,r[i].c.y);
printf("\n"); */

//sortez segmentele
qsrt(0,k-1,r);
/*
for(i=0;i<k;i++) printf("(%11ld %11.4lf %11ld %11ld)\n",
				 r[i].d,r[i].p, 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)&&
		fabs((r[i].p*r[i+1].p)+1)<0.0001)
		{nrptr++;
	 /*	printf("(%11ld %11.4lf %11ld %11ld)\n",
				 r[i].d,r[i].p*r[i+1].p, r[i].c.x,r[i].c.y);*/
		i=i+1;
		}
	}
printf("%d",nrptr);
return 0;
}