Pagini recente » Cod sursa (job #1975430) | Cod sursa (job #3000773) | Cod sursa (job #2697901) | Cod sursa (job #2651154) | Cod sursa (job #182082)
Cod sursa(job #182082)
#include<stdio.h>
#include<math.h>
double x[1502],y[1502],r3,xk,yk,eps,aux;
int n,i,j,sol;
void hd(int ic,int nc);
void sh(int i1,int i2);
int cb(int st,int dr);
int main()
{
freopen("triang.in","rt",stdin);
freopen("triang.out","wt",stdout);
eps=0.001;
r3=sqrt(3);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
for(i=n/2;i>=1;i--)hd(i,n);
for(i=n;i>=1;i--){sh(1,i);hd(1,i-1);}
for(i=1;i<=n-2;i++)
for(j=i+1;j<=n-1;j++)
{ xk=(x[i]+x[j]-(y[j]-y[i])*r3)/2;
yk=(y[i]+y[j]+(x[j]-x[i])*r3)/2;
sol+=cb(j+1,n);
xk=(x[i]+x[j]+(y[j]-y[i])*r3)/2;
yk=(y[i]+y[j]-(x[j]-x[i])*r3)/2;
sol+=cb(j+1,n);
}
printf("%d",sol);
fcloseall();
return 0;
}
void hd(int ic,int nc)
{
int is,is1;
is=2*ic;is1=is+1;
if(is>nc)return;
if(is<nc)if(x[is1]>x[is]+eps||fabs(x[is1]-x[is])<eps&&y[is1]>y[is]+eps)is=is1;
if(x[is]>x[ic]+eps||fabs(x[is]-x[ic])<eps&&y[is]>y[ic]+eps){sh(is,ic);hd(is,nc);}
}
void sh(int i1,int i2)
{
aux=x[i1];x[i1]=x[i2];x[i2]=aux;
aux=y[i1];y[i1]=y[i2];y[i2]=aux;
}
int cb(int st,int dr)
{
int mi;
if(st>dr)return 0;
mi=(st+dr)/2;
if(xk-x[mi]>eps)return cb(mi+1,dr);
if(x[mi]-xk>eps)return cb(st,mi-1);
if(yk-y[mi]>eps)return cb(mi+1,dr);
if(y[mi]-yk>eps)return cb(st,mi-1);
return 1;
}