Cod sursa(job #2924357)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 30 septembrie 2022 13:59:23
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
/// Preset de infoarena
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

pair <double, double> pct[1505];
int n, ans;
const double sinus = 0.8660254, cosinus = 0.5, eps = 1e-6;

bool egal(pair <double, double> p, double x, double y)
{
    double xdiff = p.first - x;
    double ydiff = p.second - y;
    if(-eps < xdiff && xdiff < eps && -eps < ydiff && ydiff < eps)
        return 1;
}

bool maimic(pair <double, double> p, double x, double y)
{
    double xdiff = p.first - x;
    double ydiff = p.second - y;
    if(xdiff < -eps)
        return 1;
    if(xdiff > eps)
        return 0;
    if(ydiff < -eps)
        return 1;
    return 0;
}


int cautbin(double x, double y)
{
    int aux = 0;
    for(int i = (1 << 11); i; i >>= 1)
    {
        if(aux + i > n)
            continue;
        if(egal(pct[aux + i], x, y))
            return 1;
        if(maimic(pct[aux + i], x, y))
            aux += i;
    }
    return 0;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].first >> pct[i].second;
    sort(pct + 1, pct + n + 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            double x, y, deltax, deltay;
            deltax = pct[j].first - pct[i].first;
            deltay = pct[j].second - pct[i].second;

            x = pct[i].first + deltax * cosinus - deltay * sinus;
            y = pct[i].second + deltax * sinus + deltay * cosinus;
            ans += cautbin(x, y);
            x = pct[i].first + deltax * cosinus + deltay * sinus;
            y = pct[i].second - deltax * sinus + deltay * cosinus;
            ans += cautbin(x, y);
        }
    }
    ans = ans / 3;
    fout << ans;
    return 0;
}