Cod sursa(job #1320351)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 17 ianuarie 2015 21:37:42
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax = 1000;
const int step_max = 512;

struct str{
    int x, y;
};
inline str mp( const int &x, const int &y ) {
    str sol; sol.x = x; sol.y = y;
    return sol;
}
bool str_cmp_xl( const str &x, const str &y ) {
    if ( x.x != y.x ) {
        return x.x < y.x;
    } else {
        return x.y < y.y;
    }
}


str v[nmax+1];

int main(  ) {
    int n;
    fin >> n;
    for ( int i = 1; i <= n; ++ i ) {
        string s;
        fin >> s;
        for ( int j = 0; j < (int)s.size(); ++ j ) {
            if ( s[j] >= '0' && s[j] <= '9' ) {
                v[i].x = v[i].x*10+s[j]-'0';
            }
        }
        v[i].x *= 2;
        fin >> s;
        for ( int j = 0; j < (int)s.size(); ++ j ) {
            if ( s[j] >= '0' && s[j] <= '9' ) {
                v[i].y = v[i].y*10+s[j]-'0';
            }
        }
        v[i].y *= 2;
    }
    sort(v+1, v+n+1, str_cmp_xl);

    int sol = 0;
    for ( int i = 1; i < n; ++ i ) {
        for ( int j = i+1; j <= n; ++ j ) {
            int c = 0;
            for ( int ind = 0; ind < 2; ++ ind ) {
                str aux;
                aux.x = (v[i].x+v[i].y+v[j].x-v[j].y)/2;
                aux.y = (-v[i].x+v[i].y+v[j].x+v[j].y)/2;
                int p = 0;
                for ( int step = step_max; step > 0; step /= 2 ) {
                    if ( p+step <= n && str_cmp_xl(v[p+step], aux) ) {
                        p += step;
                    }
                }
                if ( p+1 <= n && v[p+1].x == aux.x && v[p+1].y == aux.y ) {
                    ++ c;
                }
                int i_aux = i;
                i = j;
                j = i_aux;
            }
            if ( c == 2 ) {
                ++ sol;
            }
        }
    }
    fout << sol/2 << "\n";

    return 0;
}