Cod sursa(job #804192)

Utilizator veleanduAlex Velea veleandu Data 29 octombrie 2012 00:06:01
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <algorithm>
using namespace std;

    #define prec 10000
    #define max_n 15005
    #define R3 1.7320508075688
    
    int abs ( int a ){
        if ( a < 0 )
            return -a;
        return a;
    }

    struct point{
        int x,y;
    } T[max_n];

    int i,j,n,re;
    float a,b;

    bool mysort ( point a, point b ){
        if ( abs(a.x - b.x) < 8 ) {
            return a.y<b.y;
        }
        return a.x<b.x;
    }

    bool maimic ( point a, point b ){
        if ( ( abs ( a.x - b.x ) ) < 8 ){
            if ( ( abs ( a.y-b.y ) ) < 8 ){
                return 1;
            }
            return a.y<b.y;
        }
        return a.x<b.x;
    }

    void find ( point a ){
        int rez=j+1,ind;
        for ( ind=1; ind<n; ind<<=1 )
            ;
        for ( ; ind; ind>>=1 ){
            if ( ( rez+ind <=n ) ){
                if ( maimic ( T[rez+ind], a ) ) {
                    rez+=ind;
                }
            }
        }
        if ( ( abs( T[rez].x - a.x ) < 8 ) && ( abs( T[rez].y - a.y ) < 8) ){
            re++;
        }
    }


    void solve ( point a, point b ){
        // cautam punctul |c|
        point c;
        c.x=a.x + (b.x-a.x)/2.0 - ( b.y-a.y )*R3/2;
        c.y=a.y + (b.x-a.x)*R3/2 + (b.y-a.y)/2.0;
        find ( c );

        c.x=a.x + (b.x-a.x)/2.0 + ( b.y-a.y )*R3/2;
        c.y=a.y - (b.x-a.x)*R3/2 + (b.y-a.y)/2.0;
        find ( c );
    }

int main(){
        freopen ("triang.in","r",stdin);
        freopen ("triang.out","w",stdout);
    scanf ("%d", &n );
    for ( i=1; i<=n; i++ ){
        scanf ("%f %f", &a, &b );
        T[i].x=prec*a;
        T[i].y=prec*b;
    }
    sort ( T+1, T+n+1, mysort );
    for ( i=1; i<n; i++ ){
        for ( j=i+1; j<n; j++ ){
            solve ( T[i], T[j] );
        }
    }
    printf("%d", re);
    return 0;
}