Cod sursa(job #212421)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 5 octombrie 2008 14:24:25
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>
#include<math.h>
double eps=0.0001;
long n,i,j,st,dr,poz,m,patr;
double x[100007],y[100007],x1,x2,x3,x4,y1q,y2,y3,y4,xm,ym,dx,dy;
double xf,yf;
long partit(long st, long dr)
{long i,j,m;
 double pivx,pivy,aa;
 m=(st+dr)/2;
 pivx=x[m];
 pivy=y[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(x[i]<pivx||(fabs(x[i]-pivx)<eps&&y[i]<pivy));
   do{--j;} while(x[j]>pivx||(fabs(x[i]-pivx)<eps&&y[i]>pivy));
   if (i<j)
     {aa=x[i];x[i]=x[j];x[j]=aa;aa=y[i];y[i]=y[j];y[j]=aa;}
       else
     return j;
  }
}
void quicks(long st,long dr)
{long p;
 if (st<dr)
   {p=partit(st,dr);
    quicks(st,p);
    quicks(p+1,dr);
   }
}
int main()
{
 freopen("patrate3.in","r",stdin);
 freopen("patrate3.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)
    scanf("%lf%lf",&x[i],&y[i]);
 quicks(1,n);
 for(i=1;i<n;++i)
    for(j=i+1;j<=n;++j)
       if(y[i]<y[j])
       {
        x1=x[i];
        y1q=y[i];
        x3=x[j];
        y3=y[j];
        xm=(x1+x3)/2;
        ym=(y1q+y3)/2;
        dx=fabs(xm-x1);
        dy=fabs(ym-y1q);
        x2=xm-dy;
        y2=ym+dx;
        x4=xm+dy;
        y4=ym-dx;
        st=1;dr=n;poz=-1;
        while(st<=dr)
         {m=(st+dr)/2;
          if(fabs(x[m]-x2)<eps&&fabs(y[m]-y2)<eps){poz=m;break;}
            else if(x2<x[m]||(fabs(x2-x[m])<eps&&y2<y[m])){dr=m-1;}
                   else st=m+1;
         }
        if(poz!=-1)
         {
          st=1;dr=n;poz=-1;
          while(st<=dr)
           {m=(st+dr)/2;
            if(fabs(x[m]-x4)<eps&&fabs(y[m]-y4)<eps){poz=m;break;}
              else if(x4<x[m]||(fabs(x4-x[m])<eps&&y4<y[m])){dr=m-1;}
                     else st=m+1;
           }
          if(poz!=-1)++patr;
         }
       }
 printf("%ld\n",patr);
 return 0;
}