Cod sursa(job #699907)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 29 februarie 2012 21:55:15
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define EPS 0.0001
using namespace std;
void read(),solve();
vector<pair<double,int> >V[1510];
int n,i,j,sol,X,Y;
double x[1510],y[1510],dist[1510][1510],cnt,A,B;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&x[i],&y[i]);
}
void solve()
{
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			cnt=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
			V[i].push_back(make_pair(cnt,j));
			dist[i][j]=cnt;
		}
		sort(V[i].begin(),V[i].end());
	}
	for(i=1;i<=n;i++)
		for(vector<pair<double,int> >::iterator it=V[i].begin();it!=V[i].end();it++)
			for(vector<pair<double,int> >::iterator jt=it+1;jt!=V[i].end();jt++)
			{
				if(jt->first-it->first>EPS)break;
				X=it->second;
				Y=jt->second;
				if(X>Y)swap(X,Y);
				A=dist[X][Y];
				B=it->first;
				if(A<B)swap(A,B);
				if(A-B<EPS)++sol;
			}
	printf("%d\n",sol);

}