Cod sursa(job #182082)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 20 aprilie 2008 12:47:53
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#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;
}