Cod sursa(job #2892681)

Utilizator moltComan Calin molt Data 23 aprilie 2022 07:32:49
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

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

const double EPS = double(1e-3);

struct point {
    double x;
    double y;
};

int n;
vector<point> points;

bool is_equal(double a, double b) {
    return (abs(a - b) < EPS);
}

struct comp_points {
    inline bool operator()(const point &p1, const point &p2) {
        if (is_equal(p1.x, p2.x)) return p1.y < p2.y;
        return p1.x < p2.x;    
    }
};

int binary_search(point p) {
    int left = 0, right = points.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (is_equal(points[mid].x, p.x) && is_equal(points[mid].y, p.y)) return 1;
        if (points[mid].x < p.x || (is_equal(points[mid].x, p.x) && points[mid].y < p.y)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0;
}

int main()
{
    in >> n;
    for (int k = 0; k < n; ++k) {
        point p;
        in >> p.x >> p.y;
        points.push_back(p);
    }
    
    sort(points.begin(), points.end(), comp_points());

    long long res = 0;
    int m = points.size();
    for (int i = 0; i < m - 1; ++i) {
        for (int j = i + 1; j < m; ++j) {
            point p1, p2;
            p1.x = (points[i].x + points[j].x) / 2 - (sqrt(3) / 2) * (points[j].y - points[i].y);
            p1.y = (points[i].y + points[j].y) / 2 + (sqrt(3) / 2) * (points[j].x - points[i].x);
            p2.x = (points[i].x + points[j].x) / 2 + (sqrt(3) / 2) * (points[j].y - points[i].y);
            p2.y = (points[i].y + points[j].y) / 2 - (sqrt(3) / 2) * (points[j].x - points[i].x);
            res += binary_search(p1) + binary_search(p2);
        }
    }

    res /= 3;
    out << res;
}