Cod sursa(job #177230)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 12 aprilie 2008 14:41:04
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<stdio.h>
//#include<conio.h>
#include<math.h>
//#include<stdlib.h>
#define NMAX	1001

struct pct {long  x,y; };
struct rpt {long  dx,dy,min;
	    int p1,p2;
	   };

int cmp(rpt a,rpt b)
{
//long  mina,minb;
//mina=(a.dx)<a.dy?(a.dx):a.dy;
//minb=(b.dx)<b.dy?(b.dx):b.dy;
return a.min>b.min||a.min==b.min&&a.dx>b.dx;
}

void poz(int st,int dr,int &piv,rpt x[])
{int i=st,j=dr,d=0;
 rpt	t;
 while(i<j) { if(cmp(x[i],x[j]))
					{
					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,rpt x[])
{int piv;
 if(left<right) {poz(left,right,piv,x);
				 qsrt(left,piv-1,x);
				 qsrt(piv+1,right,x);
				}
}

int main()
{
//clrscr();
freopen("patrate3.in","r",stdin);
freopen("patrate3.out","w",stdout);
int n,i,j,k,nrptr;
pct	v[NMAX]={{0.0,0.0}};
rpt 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++;
	}
/*for(i=0;i<n;i++)
	printf("%11ld,%11ld\n",v[i].x,v[i].y);
  */
k=0;
for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		{
		r[k].dx=(v[i].x-v[j].x);
		if(r[k].dx<0) r[k].dx=-r[k].dx;
		r[k].dy=(v[i].y-v[j].y);
		if(r[k].dy<0) r[k].dy=-r[k].dy;
		if(r[k].dx<=r[k].dy) r[k].min=r[k].dx;
		else r[k].min=r[k].dy;
		r[k].p1=i;r[k].p2=j;
		k++;
		}
/*for(i=0;i<k;i++) printf("(%11ld,%11ld) %i %i\n",
				 r[i].dx,r[i].dy,r[i].p1,r[i].p2);
printf("\n");*/
/*
for(i=0;i<k;i++){
		if(r[i].dx<0) r[i].dx=-r[i].dx;
		if(r[i].dy<0) r[i].dy=-r[i].dy;
		}
*/
/*for(i=0;i<k;i++) printf("(%11ld,%11ld) %i %i\n",
				 r[i].dx,r[i].dy,r[i].p1,r[i].p2);
printf("\n");*/
qsrt(0,k-1,r);
for(i=0;i<k;i++) printf("(%11ld,%11ld) %i %i\n",
				 r[i].dx,r[i].dy,r[i].p1,r[i].p2);
printf("\n");
nrptr=0;
for(i=0;i<k-3;i++){
	if((r[i].dx==r[i+1].dx)&&(r[i].dy==r[i+1].dy)
	&&(r[i+2].dx==r[i+3].dx)&&(r[i+2].dy==r[i+3].dy)) {
		nrptr++;
		i=i+1;
		}
	}
printf("%d",nrptr);
return 0;
}