Cod sursa(job #1285131)

Utilizator nytr0gennytr0gen nytr0gen Data 7 decembrie 2014 10:12:15
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.48 kb
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

const char IN_FILE[]  = "patrate3.in";
const char OUT_FILE[] = "patrate3.out";

class Hash {
    private:
        const int MOD = 66923;
        vector<pair<int, int>> v[66923];

        inline int get_key(const int key1, const int key2) {
            int hash_key = key1 ^ key2;
            while (hash_key < 0) {
                hash_key += this->MOD;
            }

            return hash_key % this->MOD;
        }

    public:
        bool insert(const int key1, const int key2) {
            if (this->search(key1, key2)) {
                return false;
            }

            int hash_key = this->get_key(key1, key2);
            this->v[hash_key].push_back(make_pair(key1, key2));

            return true;
        }

        bool erase(const int key1, const int key2) {
            int hash_key = this->get_key(key1, key2);
            for (auto &it: this->v[hash_key]) {
                if (it.first == key1 && it.second == key2) {
                    it = this->v[hash_key].back();
                    this->v[hash_key].pop_back();

                    return true;
                }
            }

            return false;
        }

        bool search(const int key1, const int key2) {
            int hash_key = this->get_key(key1, key2);
            for (auto it: this->v[hash_key]) {
                if (it.first == key1 && it.second == key2) {
                    return true;
                }
            }

            return false;
        }
};

int main() {
    freopen(IN_FILE, "r", stdin);
    freopen(OUT_FILE, "w", stdout);

    int N; scanf("%d", &N);

    Hash A;
    vector<pair<int, int>> puncte;
    float x_float, y_float;
    int x, y;
    while (N--) {
        scanf("%f%f", &x_float, &y_float);
        x = x_float * 1000;
        y = y_float * 1000;

        A.insert(x, y);
        puncte.push_back(make_pair(x, y));
    }

    int patrate = 0, x1, y1, x2, y2, x3, y3, x4, y4;
    for (int i = 0; i < puncte.size(); i++) {
        for (int j = i + 1; j < puncte.size(); j++) {
            x1 = puncte[i].first; y1 = puncte[i].second;
            x2 = puncte[j].first; y2 = puncte[j].second;
            x3 = x1 + y1 - y2; y3 = y1 + x2 - x1;
            x4 = x2 + y1 - y2; y4 = y2 + x2 - x1;

            //printf("%d %d\n", A.search(x3, y3), A.search(x4, y4));
            if (A.search(x3, y3) && A.search(x4, y4)) {
                patrate++;
            }
        }
    }

    printf("%d", patrate/2);

    return 0;
}