Cod sursa(job #2754731)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 26 mai 2021 13:57:25
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>

using namespace std;

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

class Complex {
public:
    // get rid of decimals - work in scale 10^5
    Complex(int64_t re, int64_t im) : Re(re), Im(im) {}

    Complex() : Complex(0, 0) {};
    int64_t Re, Im;

    friend istream &operator>>(istream &i, Complex &cp) {
        string a, b;
        i >> a >> b;
        a.erase(a.end() - 5); // remove decimal
        b.erase(b.end() - 5);
        a += "0";
        b += "0";
        stringstream ss(a + " " + b);
        int64_t re, im;
        ss >> re >> im;
        cp = Complex(re, im);
        return i;
    }

    // debug
    friend ostream &operator<<(ostream &o, const Complex &cp) {
        o << "(" << cp.Re << ", " << cp.Im << ")";
        return o;
    }

    friend bool operator<(const Complex &a, const Complex &b) {
        return a.Re < b.Re || (a.Re == b.Re && a.Im < b.Im);
    }

    friend bool operator==(const Complex &a, const Complex &b) {
        return a.Re == b.Re && a.Im == b.Im;
    }

    friend Complex operator+(const Complex &a, const Complex &b) {
        return Complex(a.Re + b.Re, a.Im + b.Im);
    }

    friend Complex operator-(const Complex &a, const Complex &b) {
        return Complex(a.Re - b.Re, a.Im - b.Im);
    }

    friend Complex operator*(const Complex &a, const Complex &b) {
        return Complex(a.Re * b.Re - a.Im * b.Im, a.Re * b.Im + a.Im * b.Re);
    }

    static Complex mid(Complex a, Complex b) {
        return Complex((a.Re + b.Re) >> 1, (a.Im + b.Im) >> 1);
    }
};

const Complex _i = Complex(0, 1);

class {
public:
    const int P = 9997;
    vector<vector<Complex>> data;

    void init() {
        data.resize(P);
    }

    void add(Complex z) {
        int h = abs((3 * z.Re + 5 * z.Im) / 8) % P;
        data[h].push_back(z);
    }

    bool exists(const Complex &z) {
        int h = abs((3 * z.Re + 5 * z.Im) / 8) % P;
        return binary_search(data[h].begin(), data[h].end(), z);
    }
} LookupTable;

bool foundSquare(Complex a, Complex c) {
    Complex m = Complex::mid(a, c);

    // build the other corners of a potential square
    Complex b = (a - m) * _i + m;
    Complex d = (c - m) * _i + m;

    // check if b,d are in the input
    return LookupTable.exists(b) && LookupTable.exists(d);
}

int N;
vector<Complex> Points;

int main() {
    LookupTable.init();

    f >> N;
    for (int i = 0; i < N; i++) {
        Complex z;
        f >> z;
        Points.push_back(z);
    }
    sort(Points.begin(), Points.end());

    for (int i = 0; i < N; i++)
        LookupTable.add(Points[i]);

    int result = 0;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++) {
            //cout<<Points[i]<<' '<<Points[j]<<'\n';
            result += foundSquare(Points[i], Points[j]);
        }

    g << result / 2;

    return 0;
}