Cod sursa(job #457117)

Utilizator siminescuPaval Cristi Onisim siminescu Data 18 mai 2010 03:49:21
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<math.h>
using namespace std;
# define nmax 1502
# define rad3 1.7320508
# define precision 0.001
typedef struct structura{double x,y;};
structura p[nmax],aux;
int n;
ifstream f("triang.in");
ofstream g("triang.out");
void read()
{
	f>>n;int i;
	for(i=1;i<=n;i++) f>>p[i].x>>p[i].y;
}
void swap(int a,int b)
{
	structura aux=p[a];p[a]=p[b];p[b]=aux;
}
void DownHeap(int from,int to)
{
	for(int son=2*from;son<to;from=son,son=from*2)
	{
		if(son<to-1&&(p[son].x<p[son+1].x||(p[son].x==p[son+1].x&&p[son].y<p[son+1].y))) son++;
		if(p[from].x>=p[son].x||(p[from].x==p[son].x&&p[from].y>=p[son].y)) return;
		swap(from,son);
	}
}
void HeapSort(int from,int to)
{
	int i;
	for(i=(to-from)/2;i>0;i--) DownHeap(i,to);
	while(from<to)
	{
		swap(from,to-1);to--;
		DownHeap(from,to);
	}
}
int search(double a,double b,int st)
{
	int dr=n,mij;
	do
	{
		mij=(st+dr)/2;
		if(abs(p[mij].x-a)<precision&&abs(p[mij].y-b)<precision)return 1;
		if(p[mij].x<a||(p[mij].x==a&&p[mij].y<b)) st=mij+1;
		else dr=mij;
	}while(st<dr);
	return 0;
}
int main()
{
	int nr=0,i,j;
	structura x1,x2;
	read();
	HeapSort(1,n+1);
	for(i=1;i<n-1;i++)
		for(j=i+1;j<n;j++)
		{
			x1.x=(p[i].x+p[j].x-(p[i].y-p[j].y)*rad3)/2;
			x1.y=((p[i].x-p[j].x)*rad3+p[i].y+p[j].y)/2;
			x2.x=(p[i].x+p[j].x+(p[i].y-p[j].y)*rad3)/2;
			x2.y=(p[i].y+p[j].y-(p[i].x-p[j].x)*rad3)/2;
			if(search(x1.x,x1.y,j+1))nr++;
			if(search(x2.x,x2.y,j+1))nr++;
		}
	g<<nr<<'\n';
}