Cod sursa(job #1304210)

Utilizator nytr0gennytr0gen nytr0gen Data 28 decembrie 2014 19:19:49
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.82 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
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({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", &N);

    Hash A;
    vector<pair<int, int>> puncte;
    int x, y, xf, yf, xaux, yaux;
    char line[24];
    while (N--) {
        gets(line);
        sscanf(line, "%d.%d %d.%d", &x, &xaux, &y, &yaux);
        x = x * 10000 + xaux;
        y = y * 10000 + yaux;

        sscanf(line, "%f %f", &xf, &yf);
        if (xf < 0) x = -abs(x - 2 * xaux);
        if (yf < 0) y = -abs(y - 2 * yaux);

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

    // for (auto it: puncte) {
    //    printf("%d %d\n", it.first, it.second);
    // }

    int patrate = 0, x1, y1, x2, y2, x3, y3, x4, y4, mx, my;
    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;

            mx = (x1 + x2) / 2; my = (y1 + y2) / 2;
            x3 =-(y1 - my) + mx; y3 = (x1 - mx) + my;
            x4 = (y1 - my) + mx; y4 =-(x1 - mx) + my;

            //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;
}