Cod sursa(job #590664)

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

void merge(float x[1501],float 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(float x[1501],float y[1501],int p,int q,float a,float b)
{int s,i;
for(s=p;s<=q;s<<=1);
for(i=p-1;s;s>>=1)
if(i+s<=q&&x[i]<=a)
       i+=s;
if(a-x[i]<0.0001&&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("%f%f\n",&x[i],&y[i]);
merge(x,y,1,n);
for(i=1;i<n-1;i++)
      {for(j=i+1;j<n;j++)
      if(bin(x,y,j+1,n,(x[i]-x[j]-(y[i]+y[j])*rad)/2,(rad*(x[i]+x[j])-y[j]+y[i])/2))
             k++;}
printf("%d",k);
fclose(stdin);
fclose(stdout);
return 0;}