Cod sursa(job #590678)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 mai 2011 13:00:11
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 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 p,int q,double a,double b)
{int m=(p+q)/2;
if(p>q)
      return 0;
if(fabs(a-x[m])<0.001&&fabs(b-y[m])<0.001)
      return m;
if(x[m]<a)
      return bin(x,y,m+1,q,a,b);
return bin(x,y,p,m-1,a,b);}
      
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,1,n,(x[i]-x[j]-(y[i]+y[j])*rad)/2,(y[i]-y[j]+rad*(x[i]+x[j]))/2))
                    k++;
             if(bin(x,y,1,n,(-rad*(y[i]+y[j])-x[i]+x[j])/2,(y[j]-y[i]+rad*(x[i]+x[j]))/2))
                    k++;}}
printf("%d",k);
fclose(stdin);
fclose(stdout);
return 0;}