Cod sursa(job #14247)

Utilizator georgianaGane Andreea georgiana Data 8 februarie 2007 15:50:48
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <stdio.h>
#include <math.h>

#define EPS 0.0001

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

int comp(float x, float y)
{
    if (fabs(x-y)<EPS) return 0;
    if (x < y) return -1;
    return 1;
}

int compara(float Ax, float Ay, float Bx, float By)
{
  if (comp(Ax, Bx) == 0 && comp(Ay, By) == 0) return 0;
  else 
  if (comp(Ax, Bx) == -1 || (comp(Ax, Bx) == 0 && comp(Ay, By) == -1)) return -1;
  else 
  if (comp(Ax, Bx) == 1 || (comp(Ax, Bx) == 0 && comp(Ay, By) == 1)) return 1;   
  
  return 2;
}

void qSort(int st,int dr)
{
     int i=st, j=dr;
     float mx=x[(i+j)/2],my=y[(i+j)/2];
     do
     {
         while (compara(x[i],y[i],mx,my)<0) i++;
         while (compara(x[j],y[j],mx,my)>0) 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=fabs(x[i]-mx);
             dy=fabs(y[i]-my);
             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=compara(ax,ay,x[m],y[m]);
                 if (e==0) f=1,st=dr+1;
                 else if (e<0) 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=compara(bx,by,x[m],y[m]);
                 if (e==0) f=1,st=dr+1;
                 else if (e<0) 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;
}