Cod sursa(job #612164)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 6 septembrie 2011 11:33:39
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<math.h>
int i,n,j;
double x[1501],y[1501],z[1501],w[1501],a1,a2,a3,a4,r;
long long k;

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);
r=sqrt(3);
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
      {a1=(x[i]+x[j])/2+r*(y[i]-y[j])/2;
      a2=(y[i]+y[j])/2+r*(x[j]-x[i])/2;
      a3=(x[i]+x[j])/2+r*(y[j]-y[i])/2;
      a4=(y[i]+y[j])/2+r*(x[i]-x[j])/2;
      if(bin(x,y,j+1,n,a1,a2))
             k++;
      if(bin(x,y,j+1,n,a3,a4))
             k++;}
printf("%lld",k);
return 0;}