Cod sursa(job #700421)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 1 martie 2012 10:15:51
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;

int n,i,j,sol,A,B,C;
double x[1510],y[1510],dist[1510][1510],D,ab,bc,ac,eps=0.00001;
vector<pair<double,int> > V[1510];

void read(),solve();

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++)
		{
			D=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
			V[i].push_back(make_pair(D,j));
			dist[i][j]=dist[j][i]=D;
		}
		sort(V[i].begin(),V[i].end());
	}
	vector<pair<double,int> >::iterator it,iit;
	for(i=1;i<n;i++)
	{
		for(it=V[i].begin();it!=V[i].end();it++)
		{
			for(iit=it+1;iit!=V[i].end();iit++)
			{
				ab=it->first;
				ac=iit->first;
				B=it->second;
				C=iit->second;
				if(ac-ab>eps)break;
				bc=dist[B][C];
				if(abs(ab-bc)<eps)sol++;
			}
		}
	}
	printf("%d\n",sol);
}