Cod sursa(job #258134)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 14 februarie 2009 19:33:11
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<stdio.h>
#include<math.h>
#define eps 0.001
long n,i,j,st,dr,poz,m,nr;
double d,h,p,unghi,dx,dy;
struct pct{double x,y;}a[2000],M,p1,p2;
double dist(pct A,pct B)
{
 return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int vertical(pct A,pct B)
{
 return (fabs(A.x-B.x)<eps&&fabs(A.x-B.x)>=(-eps));
}
double panta(pct A,pct B)
{
 if(vertical(A,B))return 2000000000;
   else return (B.y-A.y)*1.0/(B.x-A.x);
}
int partit(pct a[ ],int st, int dr)
{int i,j,m;
 pct piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].x-piv.x<(-eps)||((a[i].x-piv.x<=eps&&a[i].x-piv.x>=(-eps))&&a[i].y-piv.y<(-eps)));
   do{--j;} while(a[j].x-piv.x>eps||((a[j].x-piv.x<=eps&&a[j].x-piv.x>=(-eps))&&a[j].y-piv.y>eps));
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(pct a[ ],int st,int dr)
{int p;
 if (st<dr)
   {p=partit(a,st,dr);
    quicks(a,st,p);
    quicks(a,p+1,dr);
   }
}
int main()
{
 freopen("triang.in","r",stdin);
 freopen("triang.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)
    scanf("%lf%lf",&a[i].x,&a[i].y);
 quicks(a,1,n);
 for(i=1;i<n;++i)
    for(j=i+1;j<=n;++j)
      {M.x=(a[i].x+a[j].x)/2;
       M.y=(a[i].y+a[j].y)/2;
       d=dist(a[i],a[j]);
       h=d*sqrt(3)/2;
       p=panta(a[i],a[j]);
       unghi=atan(p);
       dx=h*sin(unghi);
       dy=h*cos(unghi);
       p1.x=M.x+dx;
       p1.y=M.y-dy;
       p2.x=M.x-dx;
       p2.y=M.y+dy;
       st=j+1;dr=n;poz=-1;
       while(st<=dr)
        {m=(st+dr)/2;
         if(a[m].x-p1.x<=eps&&a[m].x-p1.x>=(-eps)&&a[m].y-p1.y<=eps&&a[m].y-p1.y>=(-eps))
           {poz=m;break;}
            else
         if(p1.x-a[m].x<(-eps)||(a[m].x-p1.x<=eps&&a[m].x-p1.x>=(-eps)&&p1.y-a[m].y<(-eps)))
           dr=m-1;
            else
           st=m+1;
        }
       if(poz>0)++nr;
       st=j+1;dr=n;poz=-1;
       while(st<=dr)
        {m=(st+dr)/2;
         if(a[m].x-p2.x<=eps&&a[m].x-p2.x>=(-eps)&&a[m].y-p2.y<=eps&&a[m].y-p2.y>=(-eps))
           {poz=m;break;}
            else
         if(p2.x-a[m].x<(-eps)||(a[m].x-p2.x<=eps&&a[m].x-p2.x>=(-eps)&&p2.y-a[m].y<(-eps)))
           dr=m-1;
            else
           st=m+1;
        }
       if(poz>0)++nr;
      }
 printf("%ld\n",nr);
 return 0;
}