Cod sursa(job #630902)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 6 noiembrie 2011 18:38:15
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<math.h>
#define N 1001
long n,i,r,k,j,t,l;
double x[N],y[N],a[N],b[N],mijx,mijy,dx,dy;

int cmp(double a,double b)
{return (fabs(a-b)<=0.00001);}

void merge(long p,long q)
{long i,j,k,m=(p+q)/2;
if(p==q)
       return;
merge(p,m);
merge(m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&(x[i]<x[j]||(cmp(x[i],x[j])&&y[i]<y[j]))))
       a[k]=x[i],b[k++]=y[i++];
else
       a[k]=x[j],b[k++]=y[j++];
for(i=p;i<=q;i++)
       x[i]=a[i],y[i]=b[i];}

int main()
{FILE *f=fopen("patrate3.in","r"),*g=fopen("patrate3.out","w");
fscanf(f,"%ld",&n);
for(i=1;i<=n;i++)
      fscanf(f,"%lf%lf",&x[i],&y[i]);
merge(1,n);
for(k=1;k<=n;k<<=1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
      {mijx=(x[i]+x[j])/2,mijy=(y[i]+y[j])/2;
      if(y[i]<y[j])
             {dx=fabs(mijx-x[i]),dy=fabs(mijy-y[i]);
             for(l=0,t=k;t;t>>=1)
             if(l+t<=n&&x[l+t]<=mijx+dy)
                    l+=t;
             if(cmp(x[l],mijx+dy)&&cmp(y[l],mijy-dx))
                    {for(l=0,t=k;t;t>>=1)
                    if(l+t<=n&&x[l+t]<=mijx-dy)
                           l+=t;
                    if(cmp(x[l],mijx-dy)&&cmp(y[l],mijy+dx))
                           r++;}}
      else
             {dx=fabs(mijx-x[j]),dy=fabs(mijy-y[j]);
             for(l=0,t=k;t;t>>=1)
             if(l+t<=n&&x[l+t]<=mijx-dy)
                    l+=t;
             if(cmp(x[l],mijx-dy)&&cmp(y[l],mijy-dx))
                    {for(l=0,t=k;t;t>>=1)
                    if(l+t<=n&&x[l+t]<=mijx+dy)
                           l+=t;
                    if(cmp(x[l],mijx+dy)&&cmp(y[l],mijy+dx))
                           r++;}}}
fprintf(g,"%ld",r);
return 0;}