Cod sursa(job #903899)

Utilizator Theorytheo .c Theory Data 3 martie 2013 12:35:30
Problema Patrate 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

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

const int Nmax = 1003;
const double Eps = 0.0000001;
const int Mod = 669013;

struct Point{
    double x; double y;

    bool operator ==(const Point P1)const{
        return ((P1.x - x)<Eps && (P1.y - y) < Eps);
    }
};

struct cmp{

    bool operator()(const Point &P1,const Point &P2)const{
        if((P1.x - P2.x) == 0)
            return P1.y < P2.y;
        return P1.x < P2.x;
    }
};

int N; vector<Point> V[Mod + 5]; int NumberSquares; Point M[Nmax];


bool Search(const Point &P){

    int Value = (P.x + P.y)/1;
    int Key = (Value) % Mod;

    if(Key < 0) Key += Mod;

    for(int i = 0 ; i < V[Key].size(); ++i)
        if(V[Key][i] == P) return true;

    return false;
}

void Add(const Point &P){

    int Value = (P.x + P.y)/1;
    int Key = Value % Mod;

    if(Key < 0) Key += Mod;

    V[Key].push_back(P);

}

void Read(){

    fin >> N;Point A;

    for(int i = 1; i <= N; ++i){
        fin>> A.x >> A.y;
        Add(A); M[i] = A;
    }
}

void Solve(){

    sort(M + 1, M + 1 + N, cmp());

    for(int i = 1; i < N; ++i)
        for(int j = i + 1; j <= N; ++j){

            Point C; Point D;

            double XDistance = (M[i].y - M[j].y);
            double YDistance = (M[j].x - M[i].x);

            C.x = M[j].x + XDistance; C.y = M[j].y + YDistance;
            D.x = M[i].x + XDistance; D.y = M[i].y + YDistance;


            if(Search(C) && Search(D)) ++NumberSquares;

            C.x = M[j].x - XDistance; C.y = M[j].y - YDistance;
            D.x = M[i].x - XDistance; D.y = M[i].y - YDistance ;

            if(Search(C) && Search(D)) ++NumberSquares;
        }
}

void Print(){

    fout << NumberSquares/4;
}
int main(){

    Read(); Solve(); Print();

    return 0;
}