Cod sursa(job #524414)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 21 ianuarie 2011 12:08:51
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define dim 1501
using namespace std;
float lungimi[100000000];
int sol;
int nrtri;
float cautarebinara(float x,int st,int dr)
{
	int m;
	while(st<=dr)
	{
		m=(st+dr)/2;
		if(lungimi[m]==x&&lungimi[m+1]>x)
			return m;
		if(lungimi[m]<x)
			st=m+1;
		else
			dr=m-1;
		
	}
	return 0;
}

//float x[dim],y[dim];
struct triunghi
{
	float x,y;
};
triunghi a[dim];
int nr=1;
int n;
int i,j;
float dreapta(float x1,float y1,float x2,float y2)
{
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
inline float cmp(float i,float j)
{
	return i<j;
}

int main()
{
	ifstream f("triang.in");
	//freopen ("triang.out","w",stdout);
	ofstream g("triang.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i].x>>a[i].y;
	
	for(i=1;i<n;i++)
	{
		//g<<a[i].x<<" "<<a[i].y<<"\n";
		for(j=i+1;j<=n;j++)
		{
			lungimi[nr]=dreapta(a[i].x,a[i].y,a[j].x,a[j].y);
			nr++;
		}
	}
	lungimi[nr]=10000000;
	//for(i=1;i<nr;i++)
	//	g<<lungimi[i]<<" ";
	//g<<"\n";
	sort(lungimi,lungimi+n,cmp);
//	for(i=1;i<nr;i++)
//		g<<lungimi[i]<<" ";
//  g<<"\n";
	for(i=1;i<nr;i++)
		if(lungimi[i]==lungimi[i+1])
		{
			sol=cautarebinara(lungimi[i],i,nr);
		//	g<<sol<<" ";
		if(sol>0)
				nrtri=nrtri+sol-i;
	
		}
		g<<nrtri;
				
		
		//g<<lungimi[i]<<" ";
			//if(i!=j)
			//	g<<<<"\n";
			
	//
		//g<<x[i]<<" "<<y[i]<<"\n";
		//printf("%f\n",&x[i]);
	return 0;
}