Cod sursa(job #2753100)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 21 mai 2021 01:55:07
Problema Patrate 3 Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "patrate3.in" );
ofstream fout( "patrate3.out" );

double err = 0.0000001;

int cnt = 0;

unordered_map <double, int> DIST;

unordered_map <int, vector< pair<double, double> > > H;

int HashF( double x, double y ) {
    return x * y;
}

double Distanta( double x1, double y1, double x2, double y2 ) {
    return ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 );
}

bool Egal( double a, double b ) {
    return abs( a - b ) < err;
}

bool Check_points( double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4 ) {
    if(!( abs( x1 + x2 - x3 - x4 ) < err && abs( y1 + y2 - y3 - y4 ) < err )) return false;

    double X = ( x1 + x2 + x3 + x4) / 4;
    double Y = ( y1 + y2 + y3 + y4) / 4;

    double d1 = Distanta( x1, y1, X, Y );
    double d2 = Distanta( x2, y2, X, Y );
    double d3 = Distanta( x3, y3, X, Y );
    double d4 = Distanta( x4, y4, X, Y );
    double d5 = Distanta( x1, y1, x3, y3 );
    double d6 = Distanta( x1, y1, x4, y4 );

    //fout << d1 << ' ' << d2 << ' ' << d3 << ' ' << d4 << '\n';

    return ( Egal( d1, d2 ) && Egal( d3, d4 ) && Egal( d1, d3 ) && Egal( d5, d6 ) );
}

void Check( double x1, double y1, double x2, double y2 ) {
    double x3, y3, x4, y4;
    double C;

    C = x1 + x2 - abs( y1 - y2 );

    x3 = C / 2;
    x4 = x3 + abs( y1 - y2 );

    C = y1 + y2 - abs( x1 - x2 );

    y3 = C / 2;
    y4 = y3 + abs( x1 - x2 );

    if( !Check_points( x1, y1, x2, y2, x3, y3, x4, y4 ) )
        swap( y3, y4 );

    //fout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
    //fout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 << '\n';

    int hf = HashF( x3, y3 );
    int tmp = 0;

    for( int i = 0; i < H[hf].size(); ++i )
        if( abs( H[hf][i].first - x3 ) < err && abs( H[hf][i].second - y3 ) < err ) {
            //fout << H[hf][i].first << ' ' << H[hf][i].second << '\n';

            ++tmp;
            break;
        }

    hf = HashF( x4, y4 );

    for( int i = 0; i < H[hf].size(); ++i )
        if( abs( H[hf][i].first - x4 ) < err && abs( H[hf][i].second - y4 ) < err ) {
            //fout << H[hf][i].first << ' ' << H[hf][i].second << '\n';

            ++tmp;
            break;
        }

    if( tmp == 2 )
        ++cnt;
}

int main()
{
    int N;
    vector <pair<double, double> > V;

    fin >> N;

    for( int i = 1; i <= N; ++i ) {
        double x, y;

        fin >> x >> y;

        x += 10001;
        y += 10001;

        V.push_back( { x, y } );
        H[HashF(x, y )].push_back( { x, y } );
    }

     for( int i = 0; i < V.size(); ++i )
        for( int j = i + 1; j < V.size(); ++j )
            DIST[Distanta( V[i].first, V[i].second, V[j].first, V[j].second )]++;

    for( int i = 0; i < V.size(); ++i )
        for( int j = i + 1; j < V.size(); ++j ) {
            int old = cnt;

            if( DIST[Distanta( V[i].first, V[i].second, V[j].first, V[j].second )] < 2 )
                continue;

            Check( V[i].first, V[i].second, V[j].first, V[j].second );

            //if( old != cnt )
            //    fout << i << ' ' << j << '\n';
        }

   // Check( V[3].first, V[3].second, V[5].first, V[5].second );

    fout << cnt / 2 << '\n';

    return 0;
}