Cod sursa(job #635281)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 noiembrie 2011 08:49:36
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>
#include<math.h>
#define N 1001
long n,i,k,j,r,l,t;
float x[N],y[N],a[N],b[N],mijx,mijy,dx,dy;

int cmp(float a,float b)
{return fabs(a-b)<1;}

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,"%f%f",&x[i],&y[i]),x[i]*=10000,y[i]*=10000;
merge(1,n);
for(k=1;k<=n;k<<=1);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
      {mijx=(x[i]+x[j])/2,mijy=(y[i]+y[j])/2;
      dx=fabs(mijx-x[i]),dy=fabs(mijy-y[i]);
      if(y[i]<y[j])
             {for(l=0,t=k;t;t>>=1)
             if(l+t<=n&&(x[l+t]<mijx+dy||(cmp(x[l+t],mijx+dy)&&y[l+t]<=mijy-dx)))
                    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||(cmp(x[l+t],mijx-dy)&&y[l+t]<=mijy+dx)))
                           l+=t;
                    if(cmp(x[l],mijx-dy)&&cmp(y[l],mijy+dx))
                           r++;}}
      else
             {for(l=0,t=k;t;t>>=1)
             if(l+t<=n&&(x[l+t]<mijx-dy||(cmp(x[l+t],mijx-dy)&&y[l+t]<=mijy-dx)))
                    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||(cmp(x[l+t],mijx+dy)&&y[l+t]<=mijy+dx)))
                           l+=t;
                    if(cmp(x[l],mijx+dy)&&cmp(y[l],mijy+dx))
                           r++;}}}
fprintf(g,"%ld",r);
return 0;}