Cod sursa(job #315793)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 17 mai 2009 12:39:13
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<math.h>
#define eps 0.001
struct point
{
	double x,y;
};
int n;
int f[1002];
point v[1002];

void read()
{
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&v[i].x,&v[i].y);
}

int part(int st, int dr)
{
	int i,j,m;
	point aux,p;
	m=(st+dr)>>1;
	p=v[m];
	i=st-1;
	j=dr+1;
	while(1)
	{
		do{++i;}while((p.x-v[i].x)>=eps || ((fabs(p.x-v[i].x)<eps) && (p.y-v[i].y>=eps)));
		do{--j;}while((v[j].x-p.x)>=eps || ((fabs(p.x-v[j].x)<eps) && (v[j].y-p.y>=eps)));
		if(i<j)
		{
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
		}
		else
			return j;
	}
}

void quick(int st, int dr)
{
	int p;
	if(st<dr)
	{
		p=part(st,dr);
		quick(st,p);
		quick(p+1,dr);
	}
}

int cautare(point x)
{
	int st,dr,m;
	st=1;
	dr=n;
	while(st!=dr)
	{
		m=(st+dr)>>1;
		if(((v[m].x-x.x)>=eps) || ((fabs(v[m].x-x.x)<eps) && (v[m].y-x.y)>=eps))
			dr=m;
		else
			st=m+1;
	}
	return st-1;
}

void rez()
{
	int i,j,patrate=0,poz1,poz2;
	point m,p2,p3,d;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			m.x=(v[i].x+v[j].x)*0.5;
			m.y=(v[i].y+v[j].y)*0.5;
			d.x=fabs(m.x-v[i].x);
			d.y=fabs(m.y-v[i].y);
			if((v[j].y-v[i].y)>=eps)
			{
				p2.x=m.x+d.y;
				p2.y=m.y-d.x;
				p3.x=m.x-d.y;
				p3.y=m.y+d.x;
			}
			else
			{
				//x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.
				p2.x=m.x-d.y;
				p2.y=m.y-d.x;
				p3.x=m.x+d.y;
				p3.y=m.y+d.x;
			}
			poz1=cautare(p2);
			poz2=cautare(p3);
			if((fabs(v[poz1].x-p2.x)<eps) && (fabs(v[poz1].y-p2.y)<eps))
				if((fabs(v[poz2].x-p3.x)<eps) && (fabs(v[poz2].y-p3.y)<eps))
					if(cautare(p2) && cautare(p3))
					{
						if(f[i]==0 && f[j]==0 && f[poz1]==0 && f[poz2]==0)
						{
							patrate++;
							f[i]=f[j]=f[poz1]=f[poz2]=1;
						}
					}
		}
		printf("%d\n",patrate);
}

int main()
{
	read();
	quick(1,n);
	rez();
	return 0;
}