Cod sursa(job #1358773)

Utilizator papinubPapa Victor papinub Data 24 februarie 2015 19:49:10
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
# include <fstream>
# include <cmath>
# include <algorithm>
# define DIM 1501
# define eps 1.0 / 1e4
# define rad3p2 0.8660254037
using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");
int n;
struct punct{
    double x;
    double y;
}v[DIM],aux;

inline double sqr ( double x )
{
    return x * x;
}

bool cmp ( punct a, punct b ){

    if ( abs ( a.x - b.x ) <= eps )
        return a.y < b.y;

    return a.x < b.x;
}
bool match ( punct a, punct b ){
    if ( fabs ( a.x - b.x ) <= eps && fabs ( a.y - b.y ) <= eps )
        return 1;
    return 0;
}
bool bSearch ( punct T, int x )
{
    int st = x + 1, dr = n, mid;

    while ( st <= dr ){
        mid = ( st + dr ) >> 1;

        if ( match ( T, v[mid] ) )
            return 1;

        if ( cmp ( v[mid], T ) )
            st = mid + 1;
        else
            dr = mid - 1;

    }
    return 0;
}
int main()
{
    int i,j,sol=0;
    in>>n;
    for (i=1;i<=n;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for (i=1;i<n-1;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            aux.x = ( v[i].x + v[j].x ) / 2 + rad3p2 * ( v[i].y - v[j].y );
            aux.y = ( v[i].y + v[j].y ) / 2 + rad3p2 * ( v[j].x - v[i].x );
            if ( bSearch ( aux, j ) )
                sol++;

            aux.x = ( v[i].x + v[j].x ) / 2 + rad3p2 * ( v[j].y - v[i].y );
            aux.y = ( v[i].y + v[j].y ) / 2 + rad3p2 * ( v[i].x - v[j].x );
            if ( bSearch ( aux, j ) )
                sol++;

        }
    }
    out<<sol;
    return 0;
}