Cod sursa(job #1074713)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 7 ianuarie 2014 21:39:09
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.22 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

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

const int NMAX = 1001;
const int DISP = 6613;
const int BASE = 101;
const double PREC = 0.0001;
struct Point{
    double x, y;
}V[NMAX];

vector<Point> Hash[DISP + 1];

bool cmp(const Point & A , const Point & B)
{
    if (fabs(A.x - B.x) >= PREC)
        return A.x < B.x;
    return A.y < B.y;
}

inline int getKey(Point p){
    int key = p.x;

    key = ((int)((key * BASE)%DISP + p.y)) % DISP;

    return key;
}

inline bool findPoint(Point p){
    int key = getKey(p);

    for(int i = 0 ;i < Hash[key].size(); i++){
        if( fabs(Hash[key][i].x - p.x) <= PREC && fabs(Hash[key][i].y - p.y) <= PREC)
            return true;
    }

    return false;
}

inline void addToHash(Point p){
    Hash[getKey(p)].push_back(p);
}

int main()
{
    int i, j, N, counter = 0;
    double difx, dify;
    Point point1, point2;

    in >> N;

    for(i = 0; i < N; i++){
        in >> V[i].x >> V[i].y;

        addToHash(V[i]);
    }

    sort(V , V + N , cmp);

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

            Point center;

            center.x = ( V[i].x + V[j].x )/2;
            center.y = ( V[i].y + V[j].y )/2;

            difx = fabs(center.x - V[i].x);
            dify = fabs(center.y - V[i].y);
            // Sa notam dx = abs(mijx - x0) si dy = abs(mijy - y0).
            // Se observa ca daca y0 < y1 atunci x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy iar y3 = mijy + dx.
            // In caz contrar, avem x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.

            if(V[i].y < V[j].y){
                point1.x = center.x + dify;
                point1.y = center.y - difx;

                point2.x = center.x - dify;
                point2.y = center.y + difx;
            }
            else {
                point1.x = center.x - dify;
                point1.y = center.y - difx;

                point2.x = center.x + dify;
                point2.y = center.y + difx;
            }

            if(findPoint(point1) && findPoint(point2))
                counter++;
        }

    out << counter/2 << '\n';

    return 0;
}