Cod sursa(job #3121259)

Utilizator eneagoeEugen Neagoe eneagoe Data 11 aprilie 2023 13:29:25
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#define LIMIT 1500
#define EPSILON 1e-3

using namespace std;

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

struct point {
    double long x;
    double long y;
};

point v[LIMIT];

bool point_cmp(point a, point b)
{
    return (a.x < b.x || (fabs(a.x - b.x) < EPSILON && a.y < b.y));
}

bool binsearch(point c, int left, int n)
{
    int right = n - 1;

    while(left <= right) {
        int mid = (left + right) / 2;

        if(fabs(v[mid].x - c.x) < EPSILON && fabs(v[mid].y - c.y) < EPSILON)
            return true;
        else if(point_cmp(v[mid], c))
            left = mid + 1;
        else
            right = mid - 1;
    }

    return false;
}

int main(void)
{
    int n, c = 0;

    fin >> n;

    for(auto i = 0; i < n; i++)
        fin >> v[i].x >> v[i].y;

    sort(v, v + n, point_cmp);

    for(auto i = 0; i < n; i++)
        for(auto j = i + 1; j < n - 1; j++) {
            // look for c1
            point c1, c2;
            c1.x = (v[i].x + v[j].x + sqrt(3) * (v[i].y - v[j].y)) / 2;
            c1.y = (v[i].y + v[j].y + sqrt(3) * (v[j].x - v[i].x)) / 2;

            if(binsearch(c1, j + 1, n))
                c++;

            c2.x = (v[i].x + v[j].x - sqrt(3) * (v[i].y - v[j].y)) / 2;
            c2.y = (v[i].y + v[j].y - sqrt(3) * (v[j].x - v[i].x)) / 2;
            // look for c2
            if(binsearch(c2, j + 1, n))
                c++;
        }

    fout << c;

    return 0;
}