Cod sursa(job #1798955)

Utilizator giotoPopescu Ioan gioto Data 5 noiembrie 2016 16:49:41
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#define MAX_N 1010
using namespace std;
double eps=0.00001;
int n;
struct punct
{
    double x,y;
}v[MAX_N];
bool compare( double z, double q ){

    if(fabs(z-q)<=eps) return 1;
        return 0;
}
bool caut_bin( double x0, double y0 ){

    int l = 1, r = n;
    while( l <= r )
    {
        int mid = ( l + r ) / 2;
        if( !compare(v[mid].x, x0 ) ){

            if( v[mid].x > x0 ) r = mid - 1;
                    else l = mid + 1;
            }
        else {
            if( !compare( v[mid].y, y0 ) ){

                if( v[mid].y > y0 ) r = mid - 1;
                    else l = mid + 1;
                }
            else return 1;
            }
        }
    return 0;
}
int cmp(punct p,punct r)
{
    if (p.x>r.x) return 0;
        else if (p.x==r.x && p.y>r.y) return 0;
    return 1;
}
int main()
{
    ifstream cin( "patrate3.in" );
    ofstream cout( "patrate3.out" );
    cin >> n;
    for( int i = 1; i <= n; ++i )
        cin >> v[i].x >>v[i].y;
    sort(v+1,v+n+1,cmp);
    int res = 0;
    for( int i = 1; i < n; ++i )
        for( int j = i + 1; j <= n; ++j ){

            double mijx = ( v[i].x + v[j].x ) / 2, mijy = ( v[i].y + v[j].y ) / 2;
            double dx = fabs( mijx - v[i].x ), dy = fabs( mijy - v[i].y );
            double x0, y0, x1, y1;
            if( v[i].y < v[j].y ){

                x0 = mijx + dy;
                y0 = mijy - dx;
                x1 = mijx - dy;
                y1 = mijy + dx;
                }
            else {
                x0 = mijx - dy;
                y0 = mijy - dx;
                x1 = mijx + dy;
                y1 = mijy + dx;
                }
            if( caut_bin( x0, y0 ) && caut_bin( x1, y1) ) ++res;
            }
    cout << res / 2;
    return 0;
}