Cod sursa(job #9228)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 ianuarie 2007 10:54:38
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define maxn 1010
#define baza 10000
#define maxl 30

int a[maxn],b[maxn];
int p[maxn];
int n,sol;
char v[maxl];

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

int cif(char x)
{
    return (((x>='0') && (x<='9')) || (x=='.'));
}

int find(int x,int y)
{
    int front=1,middle,back=n;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
          if ((a[p[middle]]==x) && (b[p[middle]]==y)) 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,s;
	int sx1,sx2,sy1,sy2;
	scanf("%d ",&n);

	for (i=1;i<=n;i++)
	{
        fgets(v,maxl,stdin);
        s=0;
        j=0;
        if (v[j]=='-') 
        {
            j++;
            s=1;
        }
        
        while (cif(v[j]))
        {
			if (v[j]!='.') a[i]=a[i]*10+v[j]-'0';
            j++;
        }
        
        if (s) a[i]=-a[i];

        s=0;
        j++;
        if (v[j]=='-') 
        {
            j++;
            s=1;
        }
        
        while (cif(v[j]))
        {
			if (v[j]!='.') b[i]=b[i]*10+v[j]-'0';
            j++;
        }
        
        if (s) b[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;
}