Cod sursa(job #247938)

Utilizator DraStiKDragos Oprica DraStiK Data 24 ianuarie 2009 15:39:03
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <algorithm>
using namespace std; 
#include <stdio.h>
#include <math.h>
#define DIM 1124255
struct tri {double x,y;} a[1505];
double v[DIM];
int n,m,nrt;
void read ()
{
    int i;
    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%lf%lf",&a[i].x,&a[i].y);
}
double abs (double a)
{
	if (a<0)
		return -a;
	else
    	return a;
}
double dist (int i,int j)
{
    int val;
    double nr;
	nr=sqrt ((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y));
	nr*=1000;
	val=(int)nr;
	nr=(float)val/1000;
    return nr;
}
void create ()
{
    int i,j;
    for (i=1; i<n; ++i)
        for (j=i+1; j<=n; ++j)
            v[++m]=dist (i,j);
}
int comapra (double i,double j)
{
	if (abs (i-j)>0.001)
		return 0;
	else
		return 1;
}
void search (int in,int sf,double val)
{
    int mij;
    while (in<=sf)
    {
        mij=(in+sf)/2;
        if (comapra (v[mij],val))
        {
            if ((comapra (v[mij-1],val) && mij-1>in && mij-1<sf ) || (comapra (v[mij+1],val) && mij+1>in && mij+1<sf) )
                nrt+=2;
            else
                ++nrt;
            return ;
        }
        if (v[mij]>val)
            sf=mij-1;
        else
            in=mij+1;
    }
}

int main ()
{
	freopen ("triang.in","r",stdin);
	freopen ("triang.out","w",stdout);
	int i,j;
	read ();
	create ();
	sort (v+1,v+m+1);
	for (i=1; i<m-1; ++i)
		for (j=i+1; j<m; ++j)
			if (comapra (v[i],v[j]))
                search (j+1,n,v[i]);
    printf ("%d",nrt);
    return 0;
}