Cod sursa(job #2411385)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 20 aprilie 2019 18:47:18
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>

#define llg long long
#define ldb long double

#define int_pair std::pair <int, int>
#define llg_pair std::pair <llg, llg>
#define ldb_pair std::pair <ldb, ldb>

#define x  first
#define y second

const double EPS   = 1e-5;
const double PI    = acos(-1.0f);
const double SIN60 = sin(60.0f*PI / 180.0f);
const double COS60 = cos(60.0f*PI / 180.0f);

bool equal(ldb A, ldb B) {
    return fabs(A-B) < EPS;
}

ldb_pair rotate(const ldb_pair& p1, const ldb_pair& p2) {
    ldb x = COS60 * (p1.x - p2.x) - SIN60 * (p1.y - p2.y) + p2.x;
    ldb y = SIN60 * (p1.x - p2.x) + COS60 * (p1.y - p2.y) + p2.y;
    return {x, y};
}

int N;
std::vector <ldb_pair> pts;

int count (const ldb_pair& pt) {
    int lbound = 0, rbound = N-1, mid;
    while (lbound <= rbound) {
        mid = (lbound+rbound)/2;

        if (equal(pts[mid].x, pt.x) && equal(pts[mid].y, pt.y))
            return 1;

        if (equal(pts[mid].x, pt.x))
            if (pts[mid].y > pt.y) rbound = mid-1;
            else lbound = mid+1;
        else
            if (pts[mid].x > pt.x) rbound = mid-1;
            else lbound = mid+1;
    }   return 0;
}

std::ifstream input ("triang.in");
std::ofstream output("triang.out");

void readInput() {
    input >> N;
    pts.resize(N);
    for (int i=0; i<N; ++i)
        input >> pts[i].x >> pts[i].y;
}

void solveInput() {
    std::sort(pts.begin(), pts.end());

    int ans = 0;
    for (int i=0, j; i<N; ++i)
        for (j=0; j<N; ++j) if (i != j)
            ans += count(rotate(pts[i], pts[j]));
    output << ans/3 << '\n';
}

int main()
{
    readInput();
    solveInput();

    return 0;
}