Cod sursa(job #9166)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 ianuarie 2007 21:48:17
Problema Patrate 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define maxn 1010
#define baza 10000
#define eps 0.0000001

double a[maxn],b[maxn];
int p[maxn];
int n,sol;

int cmp(int x,int y)
{
    if ((a[x]<a[y]) || ((a[x]==a[y]) && (b[x]<b[y]))) return 1;
    return 0;
}

int find(double x,double y)
{
    int front=1,middle,back=n;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
          if ((fabs(a[p[middle]]-x)<eps) && (fabs(b[p[middle]]-y)<eps)) return 1;
          
          if ((a[p[middle]]>x) || ((a[p[middle]]==x) && (b[p[middle]]>=y))) back=middle-1;
          else front=middle+1;
    }
    
    return 0;
}

int main()
{
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);

	int i,j;
	double sx1,sx2,sy1,sy2;
	scanf("%d",&n);

	for (i=1;i<=n;i++)
	{
		scanf("%lf %lf",&a[i],&b[i]);
		p[i]=i;
	}

	sort(p+1,p+n+1,cmp);
       
    for (i=1;i<=n;i++) 
      for (j=i+1;j<=n;j++) 
      {
          sx1=a[i]+b[i]-b[j];
          sy1=b[i]+a[j]-a[i];
          sx2=a[j]+b[i]-b[j];
		  sy2=b[j]+a[j]-a[i];

		  if ((find(sx1,sy1)) && (find(sx2,sy2))) sol++;

		  sx1=a[i]-b[i]+b[j];
		  sy1=b[i]-a[j]+a[i];
		  sx2=a[j]-b[i]+b[j];
		  sy2=b[j]-a[j]+a[i];

		  if ((find(sx1,sy1)) && (find(sx2,sy2))) sol++;
	  }
      
    printf("%d\n",sol/4);
    
	return 0;
}