Cod sursa(job #268047)

Utilizator DraStiKDragos Oprica DraStiK Data 28 februarie 2009 18:02:25
Problema Patrate 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#define DIM 1005
double x[DIM],y[DIM];
int n,nrt;
void read ()
{
	int i;
	scanf ("%d",&n);
	for (i=1; i<=n; ++i)
		scanf ("%lf%lf",&x[i],&y[i]);
}
void sort ()
{
	double aux;
	int i,j;
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
			if (x[i]>x[j])
			{
				aux=x[i];
				x[i]=x[j];
				x[j]=aux;
				aux=y[i];
				y[i]=y[j];
				y[j]=aux;
			}
}
double abs (double a)
{
	if (a<0)
		return -a;
	return a;
}
int cmp (double a,double b)
{
	if (abs(a-b)<=0.00001)
		return 1;
	return 0;
}
int cbin (double valx,double valy)
{
    int st=1,dr=n,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if(cmp(x[mij],valx))
        {
			if(cmp(y[mij],valy))
                return 1;
            else if(y[mij]<valy)
                st=mij+1;
            else if(y[mij]>valy)
                dr=mij-1;
        }
        else if(x[mij]<valx)
            st=mij+1;
        else if(x[mij]>valx)
            dr=mij-1;
    }
    return 0;
}
void solve ()
{
	double mijx,mijy,dx,dy,x2,x3,y2,y3;
	int i,j;
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			mijx=(x[i]+x[j])/2;
			mijy=(y[i]+y[j])/2;
			dx=abs(mijx-x[i]);
			dy=abs(mijy-y[i]);
			if (y[i]<y[j])
			{
				x2=mijx+dy;
				y2=mijy-dx;
				x3=mijx-dy;
				y3=mijy+dx;
			}
			else
			{
				x2=mijx-dy;
				y2=mijy-dx;
				x3=mijx+dy;
				y3=mijy+dx;
			}
			if (cbin (x2,y2) && cbin (x3,y3))
				++nrt;
		}
	printf ("%d",nrt/2);
}
int main ()
{
	freopen ("patrate3.in","r",stdin);
	freopen ("patrate3.out","w",stdout);
	read ();
	sort ();
	solve ();
	return 0;
}