Cod sursa(job #42388)

Utilizator raula_sanChis Raoul raula_san Data 29 martie 2007 09:52:01
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>
#include <math.h>

int N;

long Sol;

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

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

int b_search(Punct, Punct, int, int);
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;
     
	 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+1; j<=N-1; ++j)
			  {
						 if(b_search(A[i], A[j], j+1, N))
										   ++ Sol;
              }
}

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

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 b_search(Punct X, Punct Y, int ls, int ld)
{
    int m;
    
    while(ls <= ld)
    {
		 m = (ls + ld) >> 1;

		 float a = d(X, Y), b = d(X, A[m]), dif;

		 dif = b - a;
		 dif *= dif < 0 ? -1 : 1;

		 int x = (int) (dif * 1000);
		 float y = x;
		 dif = y / 1000;

		 if(!dif) return 1;

		 else
		 {
			if(d(X, A[m]) < d(X, Y))
				 ls = m + 1;
			if(d(X, A[m]) > d(X, Y))
				 ld = m - 1;
		 }
	}
    
	return 0;
}