Cod sursa(job #182046)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 20 aprilie 2008 11:25:57
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
long long x[150],y[150],r3,n,i,xk,yk,j,aux,sol;
double xx,yy;
void hd(long long ic,long long nc);
void sh(long long i1,long long i2);
long long cb(long long st,long long dr);
int main()
{
	freopen("triang.in","rt",stdin);
	freopen("triang.out","wt",stdout);
	r3=173205;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{ scanf("%lf%lf",&xx,&yy);
	  x[i]=100000*xx;y[i]=100000*yy;
	}
	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/100000)/2;
	   yk=(y[i]+y[j]+(x[j]-x[i])*r3/100000)/2;
	   sol+=cb(j+1,n);
	   xk=(x[i]+x[j]+(y[j]-y[i])*r3/100000)/2;
	   yk=(y[i]+y[j]-(x[j]-x[i])*r3/100000)/2;
	   sol+=cb(j+1,n);
	 }
	printf("%lld",sol);
	fcloseall();
	return 0;
}
void hd(long long ic,long long nc)
{
	long long is,is1;
	is=2*ic;is1=is+1;
	if(is>nc)return;
	if(x[is1]>x[is]||(x[is1]==x[is]&&y[is1]>y[is]))is=is1;
	if(x[is]>x[ic]||(x[is]==x[ic]&&y[is]>y[ic])){sh(is,ic);hd(is,nc);}
}
void sh(long long i1,long long i2)
{
	aux=x[i1];x[i1]=x[i2];x[i2]=aux;
	aux=y[i1];y[i1]=y[i2];y[i2]=aux;
}
long long cb(long long st,long long dr)
{
	long long mi;
	if(st>dr)return 0;
	mi=(st+dr)/2;
	if(xk-x[mi]>10)return cb(mi+1,dr);
	if(x[mi]-xk>10)return cb(st,mi-1);
	if(yk-y[mi]>10)return cb(mi+1,dr);
	if(y[mi]-yk>10)return cb(st,mi-1);
	return 1;
}