Cod sursa(job #2988475)

Utilizator rastervcrastervc rastervc Data 4 martie 2023 18:26:48
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

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

constexpr double EPS = 1e-6;

static inline bool equal(double x, double y) {
    return fabs(y - x) < EPS;
}

struct Vector {
    double x, y;

    Vector() noexcept : x(), y() {}
    Vector(double x, double y) : x(x), y(y) {}
    Vector(const Vector& vec) : x(vec.x), y(vec.y) {}

    inline void operator =(const Vector& vec) {
        x = vec.x, y = vec.y;
    } 

    inline bool operator ==(const Vector& vec) {
        return equal(x, vec.x) && equal(y, vec.y);
    }

    inline bool operator <(const Vector& vec) {
        return x < vec.x || (equal(x, vec.x) && y < vec.y);
    }
};

struct Matrix {
    double a, b, c, d;

    Matrix() : a(), b(), c(), d() {}
    Matrix(double a, double b, double c, double d)
        : a(a), b(b), c(c), d(d) {}
    
    static inline Matrix rotation(double theta) {
        return Matrix(
            cos(theta), -sin(theta),
            sin(theta), cos(theta)
        );
    }
};

static inline Vector operator +(const Vector& u, const Vector& v) {
    return Vector(u.x + v.x, u.y + v.y);
}

static inline Vector operator -(const Vector& u, const Vector& v) {
    return Vector(u.x - v.x, u.y - v.y);
}

static inline Vector operator *(const Matrix& M, const Vector& v) {
    return Vector(M.a * v.x + M.b * v.y, M.c * v.x + M.d * v.y);
}

static inline bool binsearch(int N, Vector vec[], const Vector& u) {
    int l = 1, r = N;
    while (l <= r) {
        const int mid = (l + r) >> 1;
        if (vec[mid] == u) return true;
        else if (vec[mid] < u) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}

constexpr int LIM = 1505;
constexpr double PI = 3.14159265359;
const Matrix R60 = Matrix::rotation(PI / 3);
const Matrix RI60 = Matrix::rotation(-PI / 3);
Vector vec[LIM];
int N, i, j, cnt;

int main() {
    fin >> N;
    for (i = 1; i <= N; ++i)
        fin >> vec[i].x >> vec[i].y;

    sort(vec + 1, vec + N + 1);

    for (i = 1; i < N; ++i)
        for (j = i + 1; j <= N; ++j) {
            const Vector vertex1 = vec[i] + R60 * (vec[j] - vec[i]);
            const Vector vertex2 = vec[i] + RI60 * (vec[j] - vec[i]);
            if (binsearch(N, vec, vertex1)) ++cnt;
            if (binsearch(N, vec, vertex2)) ++cnt;
        }

    fout << cnt / 3;

    fin.close();
    fout.close();
    return 0;
}