Cod sursa(job #147416)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 2 martie 2008 21:27:44
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define fin  "triang.in"
#define fout "triang.out"

#define EPS 0.0000001

struct dot { double X,Y; };

const int Nmax = 1510;

int N,cnt;
dot v[ Nmax ];

double absf( double a )
{
	if ( a < 0 )
		a = a * (-1.0);
	return a;
}

inline int sort_cmp( dot *A, dot *B)
{
	if ( absf( A->X - B->X ) < EPS )
		return A->Y > B->Y;
	else
		return A->X > B->X;
}

void readdata()
{
	int i;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%d",&N);

	for ( i = 0; i < N; ++i )
		scanf("%lf%lf",&v[i].X,&v[i].Y);
}

inline int cmp_search(dot A,dot B)
{
    if ( absf(A.X - B.X) < EPS )
    {
         if ( absf(A.Y - B.Y) < EPS )
             return 0;
         if ( A.Y < B.Y )
             return -1;
         else
             return  1; 
    }
    
    if ( A.X < B.X )    
       return -1;
    else
       return  1;
}

inline int search(dot A)
{
     int lo,hi,mid,val;
     
     lo = 0; hi = N - 1;
     
     while ( lo < hi )
     {
           mid = ( lo + hi ) / 2;
           
           val = cmp_search(A,v[mid]);
           
           if ( val == 0 )
              return 1;
              
           if ( val == -1 )
              hi = mid - 1;
           else
              lo = mid + 1;
     }
     
     return 0;     
}

void solve()
{
    int i,j;
    double angle;
    dot pct;
    
	qsort(v, N, sizeof(dot), (int(*)(const void*,const void*)) sort_cmp );

    angle = 60.0 * 3.14159265 / 180.0;
    
    for ( i = 0; i < N; ++i )
        for ( j = i + 1; j < N; ++j )
        {
            pct.X = ( v[j].X - v[i].X ) * cos(angle) - ( v[j].Y - v[i].Y ) * sin(angle) + v[i].X;
            pct.Y = ( v[j].X - v[i].X ) * sin(angle) + ( v[j].Y - v[i].Y ) * cos(angle) + v[i].Y;
            
            cnt += search(pct);
            
            pct.X = ( v[i].X - v[j].X ) * cos(angle) - ( v[i].Y - v[j].Y ) * sin(angle) + v[j].X;
            pct.Y = ( v[i].X - v[j].X ) * sin(angle) - ( v[i].Y - v[j].Y ) * sin(angle) + v[j].Y;
                               
            cnt += search(pct);
        }
        
    printf("%d\n",cnt);
}

int main()
{

	readdata();
	solve();

	return 0;
}