Cod sursa(job #603135)

Utilizator SmarandaMaria Pandele Smaranda Data 14 iulie 2011 17:46:01
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define eps 0.0001
using namespace std;
struct POINT
{
	float x,y;
};
POINT P[1001];
inline bool cmp (POINT A , POINT B)
{
	if (A.x-B.x>eps)
		return false;
	if (A.x-B.x<=-eps)
		return true;
	if (fabs(A.x-B.x)<=eps)
		if (A.y-B.y<=-eps)
			return true;
		else
			return false;
} 

long cautbin (long st , long dr , POINT V)
{
	long m;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (fabs(P[m].x-V.x)<=eps && fabs(P[m].y-V.y)<=eps)
			return m;
		if (P[m].x-V.x<=-eps)
			st=m+1;
		if (P[m].x-V.x>eps)
			dr=m-1;
		if (fabs(P[m].x-V.x)<=eps)
			if (P[m].y-V.y<=-eps)
				st=m+1;
			else
				dr=m-1;
	}
	return -1;
}

int main()
{
	long n,i,j,num=0,k1,k2;
	POINT A,B;
	double dy,dx;
	
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%f%f",&P[i].x,&P[i].y);
	sort(P+1,P+1+n,cmp);
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			dy=fabs(P[j].y-P[i].y);
			dx=fabs(P[j].x-P[i].x);
			A.x=P[j].x+dy;
			A.y=P[j].y-dx;
			B.x=P[i].x+dy;
			B.y=P[i].y-dx;
			k1=cautbin(1,n,A);
			k2=cautbin(1,n,B);
			if (k1!=-1 && k2!=-1)
				num++;
		}
	printf("%ld\n",num);
	return 0;
}