Cod sursa(job #590673)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 mai 2011 12:25:02
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<math.h>
#define rad 1.732050
int i,n,k=0,j;
double x[1501],y[1501],z[1501],w[1501];

void merge(double x[1501],double y[1501],int p,int q)
{int m=(p+q)/2,i,j,k;
if(p==q)
      return;
merge(x,y,p,m);
merge(x,y,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))))
      {z[k]=x[i];
      w[k++]=y[i++];}
else
      {z[k]=x[j];
      w[k++]=y[j++];}
for(i=p;i<=q;i++)
      {x[i]=z[i];
      y[i]=w[i];}}
      
int bin(double x[1501],double y[1501],int q,double a,double b)
{int s,i;
for(s=1;s<=q;s<<=1);
for(i=0;s!=0;s>>=1)
if(i+s<=q&&x[i]<=a)
       i+=s;
if(a-x[i]<0.0001&&fabs(b-y[i])<0.0001)
       return i;
return 0;}
      
int main()
{freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
      scanf("%lf%lf",&x[i],&y[i]);
merge(x,y,1,n);
for(i=1;i<=n;i++)
      {for(j=i+1;j<=n;j++)
      if(bin(x,y,n,(x[i]-x[j]+(y[i]+y[j])*rad)/2,(y[i]-y[j]-rad*(x[i]+x[j]))/2)!=0)
             k++;
      else
             if(bin(x,y,n,(rad*(y[i]+y[j])-x[i]+x[j])/2,(y[j]-y[i]-rad*(x[i]+x[j]))/2)!=0)
                    k++;}
printf("%d\n",k);
fclose(stdin);
fclose(stdout);
return 0;}