Cod sursa(job #635300)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 noiembrie 2011 09:59:30
Problema Patrate 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 1001
long n,i,r,k,j,t,l,a[N],b[N],mijx,mijy,dx,dy,x[N],y[N],o;
double c[N],d[N];

int cmp(long a,long b)
{return (abs(b-a)<=10);}

void merge(long x[N],long y[N],long p,long q)
{long i,j,k,m=(p+q)/2;
if(p==q)
       return;
merge(x,y,p,m);
merge(x,y,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",&c[i],&d[i]);
      x[i]=(long)ceil(100000*c[i])-(long)(ceil(100000*c[i]))%2;
      y[i]=(long)ceil(100000*d[i])-(long)(ceil(100000*d[i]))%2;}
merge(x,y,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=abs(mijx-x[i]),dy=abs(mijy-y[i]);
      if(y[i]<y[j])
             {for(o=i,t=k;t;t>>=1)
             if(o+t<=n&&(x[o+t]<mijx+dy||(cmp(x[o+t],mijx+dy)&&y[o+t]<=mijy-dx)))
                    o+=t;
             if(cmp(x[o],mijx+dy)&&cmp(y[o],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(o=j,t=k;t;t>>=1)
             if(o+t<=n&&(x[o+t]<mijx-dy||(cmp(x[o+t],mijx-dy)&&y[o+t]<=mijy-dx)))
                    o+=t;
             if(cmp(x[o],mijx-dy)&&cmp(y[o],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;}