Cod sursa(job #42767)

Utilizator raula_sanChis Raoul raula_san Data 29 martie 2007 15:10:33
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>
#include <math.h>

int N, step;

long Sol;

struct Punct
{ double x, y; } A[1501];

void Read();
void Solve();
void Write();

int bsearch(int, int, double);
int ok(double, double);

double d(Punct, Punct);

int main()
{
    Read();
    Solve();
    Write();
    
    return 0;
}

void Read()
{
     freopen("triang.in", "r", stdin);
     
	 scanf("%d", &N);
     
	 int i;

	 for(i=1; i<=N; ++i)
			  scanf("%lf %lf", &A[i].x, &A[i].y);

	 fclose(stdin);
}

void Solve()
{
	int i, j, k, l, found;
	double dist;
	
	for(i=1; i<N; ++i)
		for(j=i+1; j<=N; ++j)
			if(A[i].x > A[j].x || (A[i].x == A[j].x && A[i].y > A[j].y))
			{
				Punct aux;
				aux = A[i];
				A[i] = A[j];
				A[j] = aux;
			}
	
	for(i=1; i<=N-2; ++i)
		for(j=i+2; j<=N; ++j)
		{
			k = bsearch(i+1, j, (A[i].x+A[j].x)/2);
			dist = d(A[i], A[j]);
			
			if(k)
			{
				found = 0;
				for(l=k; l<=j&&A[l].x==A[k].x; ++l)
					if(ok(d(A[l], A[i]), dist) && ok(d(A[l], A[j]), dist))
					{
						found = 1;
						break;
					}
				Sol += found;
			}
		}
}

void Write()
{
     freopen("triang.out", "w", stdout);
     
     printf("%ld", Sol);
     
     fclose(stdout);
}

int bsearch(int l, int r, double value)
{
	int n = (r-l+1), step, i;
	
	for(step=1; step<=n; step<<=1);
	
	for(i=l; step; step>>=1)
		if(i+step <= r && A[i+step].x <= value)
			i += step;
	
	if(A[i].x == value)
		return i;
	
	return 0;
}

double d(Punct A, Punct B)
{
	return
		sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

int ok(double a, double b)
{
	double c, y;
	int x;
	
	c = a > b ? a - b : b - a;
	
	x = (int) (c * 10);
	y = x;
	
	c = y / 10;
	
	return !c;
}