Cod sursa(job #589166)

Utilizator stef93Stefan Gilca stef93 Data 11 mai 2011 12:38:38
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

int n,nrt;
struct P{double x,y;}a[1503];

double dist(P x,P y)
{
	return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}

bool equal(double x,double y)
{
	if (fabs(x-y)>1e-3)return 0;
	return 1;
}

bool compare(P t, P yt)
{
	return t.x>yt.x;
}

int binary_search(P t,P t1)
{
	int step,i;
	double dis;
	dis=dist(t,t1);
	for(step=1,i=0;step<n;step<<=1)
		if((i+step<n) &&((t.x<t1.x)&&(a[i+step].x>t1.x)) && (dis<=dist(t1,a[i+step])) && (dis<=dist(t,a[i+step]))) i+=step;
	if(equal(dis,dist(t1,a[i]))&&equal(dis,dist(t,a[i]))) return 1;
		return 0;
}
		

int main()
{
	int i,j,k;
	ifstream in("triang.in");
	in>>n;
	for(i=0;i<n;i++)
		in>>a[i].x>>a[i].y;
	in.close();
	sort(a,a+n,compare);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
				if(binary_search(a[i],a[j]))
					nrt++;
	ofstream("triang.out")<<nrt<<'\n';
	return 0;
}