Cod sursa(job #8754)

Utilizator georgianaGane Andreea georgiana Data 25 ianuarie 2007 15:36:25
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>

float x[1000],y[1000];
long int n,nr;

int egal(double x, double y)
{
    if (x-y<0.00001 && y-x<0.00001) return 1;
    else return 0;
}

void qSort(int st,int dr)
{
     int i=st, j=dr;
     float mx=x[(i+j)/2],my=y[(i+j)/2];
     do
     {
         while (x[i]<mx || (egal(x[i],mx) && y[i]<my)) i++;
         while (x[j]>mx || (egal(x[j],mx) && y[j]>my)) j--;
         if (i<=j)
         {
             float aux=x[i]; x[i]=x[j]; x[j]=aux;
                   aux=y[i]; y[i]=y[j]; y[j]=aux;
             i++; j--;         
         }
     } 
     while (i<=j);
     if (st<j) qSort(st,j);
     if (i<dr) qSort(i,dr);
}

int main()
{
    freopen("patrate3.in","r",stdin);
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%f %f",&x[i],&y[i]);
    qSort(0,n-1);
    nr=0;
    for (int i=0;i<n;i++)
         for (int j=i+1;j<n;j++)
              if (i!=j)
         {
             float mx,my,dx,dy,ax,bx,ay,by;
             mx=(x[i]+x[j])/2;
             my=(y[i]+y[j])/2;
             dx=x[i]-mx; if (dx<0) dx=-dx;
             dy=y[i]-my; if (dy<0) dy=-dy;
             if (y[i]<y[j])
             {
             ax=mx+dy;
             ay=my-dx;
             bx=mx-dy;
             by=my+dx;
             }
             else
             {
             ax=mx-dy;
             ay=my-dx;
             bx=mx+dy;
             by=my+dx;
             }
             int st=0, dr=n-1, f=0;
             while (st<=dr)
             {
                 int m=(st+dr)/2, e=egal(ax,x[m]);
                 if (e && egal(ay,y[m])) f=1,st=dr+1;
                 else if (ax<x[m] || (e && ay<y[m])) dr=m-1;
                 else st=m+1;
             }
             if (f==0) continue;
             st=0, dr=n-1, f=0;
             while (st<=dr)
             {
                 int m=(st+dr)/2, e=egal(bx,x[m]);
                 if (e && egal(by,y[m])) f=1,st=dr+1;
                 else if (bx<x[m] || (e && by<y[m])) dr=m-1;
                 else st=m+1;
             }
             if (f!=0) nr++;
         }   
    freopen("patrate3.out","w",stdout);
    printf("%d\n",nr/2);
    fclose(stdout);
    return 0;
}